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;
}