ORDERSET - Order statistic set
Tác giả: hieult
Ngôn ngữ: C++
#include <stdlib.h>
#include <stdio.h>
//#include <conio.h>
struct t_query
{
char type;
int param;
int porder;
} ;
int queries;
t_query query[200010];
void read_input()
{
char s[16];
scanf("%d",&queries);
for(int i = 0;i<queries;i++)
{
scanf("%s",s);
query[i].type = s[0];
scanf("%d",&query[i].param);
}
}
int compare_queries( const void *ptr1, const void *ptr2)
{
return query[*((int *)ptr1)].param - query[*((int *)ptr2)].param;
}
int qorder[200010],value[200010],distinct;
void find_order()
{
for(int i = 0;i<queries;i++) qorder[i] = i;
qsort(qorder,queries,sizeof(int),compare_queries);
query[qorder[0]].porder = 0;
value[0] = query[qorder[0]].param;
distinct = 1;
for(int i = 1;i<queries;i++)
{
if(query[qorder[i]].param!=query[qorder[i-1]].param){
query[qorder[i]].porder = query[qorder[i-1]].porder+1;
value[distinct++] = query[qorder[i]].param;
}
else query[qorder[i]].porder = query[qorder[i-1]].porder;
}
}
int norm,present[1<<19],totpresent;
void init_present()
{
for(norm = 1;norm<distinct;norm*=2);
for(int i = 1;i<2*norm;i++) present[i] = 0;
totpresent = 0;
}
void insert_value(int v)
{
int i = norm+v;
if(present[i]) return;
for(;i;i/=2) present[i]++;
totpresent++;
}
void delete_value(int v)
{
int i = norm+v;
if(!present[i]) return;
for(;i;i/=2) present[i]--;
totpresent--;
}
int kth_value(int root, int size, int k){
if((root == 1) && (k>present[root])) return -1;
if(size == 1) return root-norm;
if(k<=present[2*root]) return kth_value(2*root,size/2,k);
else return kth_value(2*root+1,size/2,k-present[2*root]);
}
int count_smaller(int root,int size, int v)
{
if(v==0) return 0;
if(v<size/2) return count_smaller(2*root,size/2,v);
else return present[2*root]+count_smaller(2*root+1,size/2,v-size/2);
}
int main()
{
// freopen("ORDERSET.in","r",stdin);
int q,i;
read_input();
find_order();
init_present();
for(q = 0;q<queries;q++) switch(query[q].type)
{
case 'I' : insert_value(query[q].porder); break;
case 'D' : delete_value(query[q].porder); break;
case 'K':
{
i = kth_value(1,norm,query[q].param);
if(i<0) printf("invalid\n");
else printf("%d\n",value[i]);
break;
}
case 'C':
{
printf("%d\n",count_smaller(1,norm,query[q].porder));
break;
}
}
// getch();
}