ORDERSET - Order statistic set

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
using namespace std;

struct Instruction {
	char c;
	int x;
};

int Q;
Instruction a[200020];
char buf[100];
int ds[200020], nd;
int sum[200020 * 4], value[200020];

void add(int n, int l, int r, int p, int v) {
	sum[n] += v;
	if(l<r) {
		int m = (l+r) / 2;
		if(p<=m) add( 2*n, l, m, p, v);
		else add( 2*n+1, m+1, r, p, v);
	}
}

int dem(int n, int l, int r, int x) {
	if(ds[r] < x) return sum[n];
	if(ds[l] >= x) return 0;
	if(l<r) {
		int m = (l+r) / 2;
		return dem( 2*n, l, m, x) + dem( 2*n+1, m+1, r, x);
	}
}

int getK(int n, int l, int r, int k) {
	if(k > sum[n]) return -1;
	if(l==r) return l;
	int m = (l+r) / 2;
	if(sum[2*n] >= k) return getK( 2*n, l, m, k);
	else return getK( 2*n+1, m+1, r, k - sum[2*n]);
}

int main() {
	scanf("%d", &Q);
	for(int i=0;i<Q;++i) {
		gets(buf);
		scanf("%c %d", &a[i].c, &a[i].x);
	}
	for(int i=0;i<Q;++i) if(a[i].c=='I') ds[nd++] = a[i].x;
	sort( ds, ds+nd);
	nd = unique(ds, ds+nd) - ds;
	for(int i=0;i<Q;++i) {
		if(a[i].c=='I') {
			int pos = lower_bound(ds, ds+nd, a[i].x) - ds;
			if(value[pos]==0) add( 1, 0, nd-1, pos, 1), value[pos] = 1;
		}
		else if(a[i].c=='D') {
			int pos = lower_bound( ds, ds+nd, a[i].x) - ds;
			if(pos < nd && ds[pos] == a[i].x && value[pos]==1)
				add( 1, 0, nd-1, pos, -1), value[pos] = 0;
		}
		else if(a[i].c=='K') {
			int pos = getK( 1, 0, nd-1, a[i].x);
			if(pos < 0 || pos >= nd) printf("invalid\n");
			else printf("%d\n", ds[pos]);
		}
		else if(a[i].c=='C') {
			int res = dem( 1, 0, nd-1, a[i].x);
			printf("%d\n", res);
		}
	}
	return 0;
}

Download