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