ORDERSET - Order statistic set

Tác giả: flashmt

Ngôn ngữ: C++

#include<iostream>
#include<algorithm>
#define maxn 200020
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec
{
   int v,p,q;
};
int n,m,a[maxn],b[maxn],e[maxn],g[maxn*5],h[maxn*5];
rec c[maxn];
char ch;

void put(int nd,int l,int r,int x,int y,int v)
{
     if (l==x && r==y) g[nd]+=v; 
     else
     {
         int mid=(l+r)/2;
         if (x<=mid) put(nd*2,l,mid,x,min(y,mid),v);
         if (y>mid) put(nd*2+1,mid+1,r,max(x,mid+1),y,v);
     }
     h[nd]=g[nd];
     if (r>l) h[nd]+=h[nd*2+1];
}

int get(int nd,int l,int r,int k)
{
    if (l==r) return l;
    int mid=(l+r)/2;
    k-=g[nd];
    if (h[nd*2]>=k) return get(nd*2,l,mid,k);
    return get(nd*2+1,mid+1,r,k);
}

int calc(int nd,int l,int r,int x)
{
    if (l==r) return g[nd];
    int mid=(l+r)/2;
    if (x<=mid) return (calc(nd*2,l,mid,x)+g[nd]);
    return (calc(nd*2+1,mid+1,r,x)+g[nd]);
}

bool cmp(rec i,rec j)
{
     return (i.v<j.v);
}

int main()
{
    int i,x;
    scanf("%d\n",&n);
    fr(i,1,n)
    {
       scanf("%c%d\n",&ch,&a[i]);
       switch (ch)
       {
          case 'I': b[i]=0; break;
          case 'D': b[i]=1; break;
          case 'K': b[i]=2; break;
          default: b[i]=3; a[i]--;
       }
       c[i].v=a[i]; c[i].p=i; c[i].q=b[i];
    }
    sort(c+1,c+n+1,cmp);
    m=0; c[0].v=-2000000000;
    fr(i,1,n)
    {
       if (c[i].q==2) continue;
       if (c[i].v>c[m].v) c[++m]=c[i];
       a[c[i].p]=m;
    }
    fr(i,1,n)
    {
        switch (b[i])
        {
           case 0: if (!e[a[i]])
                   {
                      put(1,1,m,a[i],m,1);
                      e[a[i]]=1;
                   }
                   break;
           case 1: if (e[a[i]] && a[i])
                   {
                      put(1,1,m,a[i],m,-1);
                      e[a[i]]=0;
                   }
                   break;
           case 2: if (a[i]>h[1]) printf("invalid\n");
                   else
                   {
                       x=get(1,1,m,a[i]);
                       printf("%d\n",c[x]);
                   }
                   break;
           default: if (a[i]) x=calc(1,1,m,a[i]);
                    else x=0;
                    printf("%d\n",x); 
        }
    }
    return 0;
}

Download