妈蛋真作死

TAT好长时间没打treap昨天打了下真是跪烂了……&&&（删除那个竟然写成if(o->ch[0]==NULL) o=o->ch[0];这种低级错误了卡了一晚上……）

以下注意：

1、maintain()在roate() insert() remove()的最后

2、就是上面提到的删除那块……

代码：（SPOJ 3273，treap果然效率高，4s完爆其他7s）

  1 #include<cstring>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<ctime>
  5 using namespace std;
  6 struct wjmzbmr
  7 {
  8     wjmzbmr* ch[2];
  9     int size,key,value;
 10     int cmp(int x) const
 11     {
 12         if(key==x) return -1;
 13         return key<x;
 14     }
 15     void maintain()
 16     {
 17         size=1;
 18         if(ch[0]!=NULL) size+=ch[0]->size;
 19         if(ch[1]!=NULL) size+=ch[1]->size;
 20     }
 21 };
 22 void rotate(wjmzbmr* &o,int d)
 23 {
 24     wjmzbmr* k=o->ch[d^1];
 25     o->ch[d^1]=k->ch[d];
 26     k->ch[d]=o;
 27     o->maintain();
 28     k->maintain();
 29     o=k;
 30 }
 31 void insert(wjmzbmr* &o,int x)
 32 {
 33     if(o==NULL) 
 34     {
 35         o=new wjmzbmr();
 36         o->ch[0]=o->ch[1]=NULL;
 37         o->key=x;
 38         o->value=rand()%1000000000;
 39     }
 40     else
 41     {
 42         int d=o->cmp(x);
 43         if(d==-1) return;
 44         insert(o->ch[d],x);
 45         if(o->ch[d]->value>o->value) rotate(o,d^1);
 46     }
 47     o->maintain();
 48 }
 49 void remove(wjmzbmr* &o,int x)
 50 {
 51     if(o==NULL) return;
 52     int d=o->cmp(x);
 53     wjmzbmr* t=o;
 54     if(d==-1)
 55     {
 56         if(o->ch[0]==NULL) o=o->ch[1],delete t;
 57         else
 58             if(o->ch[1]==NULL) o=o->ch[0],delete t;
 59             else
 60             {
 61                 int d1=(o->ch[0]->value>o->ch[1]->value);
 62                 rotate(o,d1);
 63                 remove(o->ch[d1],x);
 64             }
 65     }else remove(o->ch[d],x);
 66     if (o!=NULL) o->maintain();
 67 }
 68 int kth(wjmzbmr* o,int k)
 69 {
 70     int left=0;
 71     if(o->ch[0]!=NULL) left=o->ch[0]->size;
 72     if(left+1==k) return o->key;
 73     if(left+1>k) return kth(o->ch[0],k);
 74     if(left+1<k) return kth(o->ch[1],k-left-1);
 75 }
 76 int rank(wjmzbmr* o,int x)
 77 {
 78     if(o==NULL) return 0;
 79     int left=0;
 80     if(o->ch[0]!=NULL) left=o->ch[0]->size;
 81     if(x==o->key) return left;
 82     if(x<o->key) return rank(o->ch[0],x);
 83     if(x>o->key) return left+1+rank(o->ch[1],x);
 84 }
 85 int main()
 86 {    int q;
 87     scanf("%d
",&q);
 88     wjmzbmr* root=NULL;
 89     for(int i=1;i<=q;++i)
 90     {
 91         char c;
 92         int x;
 93         scanf("%c %d
",&c,&x);
 94         if(c=='I') insert(root,x);
 95         if(c=='D') remove(root,x);
 96         if(c=='K') 
 97             if(root==NULL||root->size<x) printf("invalid
");else printf("%d
",kth(root,x));
 98         if(c=='C') printf("%d
",rank(root,x));
 99     }
100     return 0;    
101 }

View Code