ORDERSET - Order statistic set

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
using namespace std;

const int Q = 200000 + 2;
int val[Q], nVal, qry[Q][2], q, bit[Q+Q], hgBit; //highestBit

void enter() {
	char s[2];
	scanf("%d", &q);
	for(int i = 0; i < q; ++i) {
		scanf("%s%d", s, &qry[i][1]);
		qry[i][0] = s[0];
		if(s[0] == 'I') val[nVal++] = qry[i][1];
	}
}

void add(int i, int v) { for(; i <= hgBit + hgBit; i += i & -i) bit[i] += v; }
int read(int i) {
	int res = bit[i], z = i - (i & -i);
	for(int v = i - 1; v != z; v -= v & -v) res -= bit[v];
	return res;
}
int sum(int i) {
	int res = 0;
	for(; i > 0; i -= i & -i) res += bit[i];
	return res;
}
int lowerBound(int fre) {
	int bitmask = hgBit, idx = hgBit << 1;
	while(bitmask != 0 && idx > 0) {
		int tIdx = idx - bitmask;
		if(fre <= bit[tIdx]) idx = tIdx;
		else fre -= bit[tIdx];
		bitmask >>= 1;
	}
	return idx;
}

void solve() {
	sort(val, val + nVal); nVal = unique(val, val + nVal) - val;
	hgBit = nVal; while(hgBit & (hgBit - 1)) hgBit -= hgBit & -hgBit;
	int n = 0;
	for(int i = 0, v, *t; i < q; ++i) switch(qry[i][0]) {
		case 'I':
			v = lower_bound(val, val + nVal, qry[i][1]) - val + 1;
			if(read(v) == 0) add(v, 1), ++n;
			break;
		case 'D':
			t = lower_bound(val, val + nVal, qry[i][1]);
			if(*t == qry[i][1]) {
				v = t - val + 1;
				if(read(v) == 1) add(v, -1), --n;
			}
			break;
		case 'C':
			v = lower_bound(val, val + nVal, qry[i][1]) - val;
			printf("%d\n", sum(v));
			break;
		case 'K':
			if(qry[i][1] > n) printf("invalid\n");
			else printf("%d\n", val[lowerBound(qry[i][1]) - 1]); 
			break;
	}
}

int main() {
	enter();
	solve();
	return 0;
}

Download