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

    

Download