SPOJ3273(Treap)

題意：給定n個操作，I,D,K,C,分別代表插入，刪除，找第K大元素，找小於x的元素個數。   分析：這裡插入，刪除和找第K大元素很簡單，直接就是模版，但是這裡找小於x的元素個數不好處理。 因為Rank(Treap *t,int x)返回的是元素x在Treap中的排名，所以這裡要求x在Treap一定是存在的，但是找小於x的元素個 數，這裡的x不一定在Treap中。   後來我想到了一個方法，就是在查找之前，我們先查找x在Treap中是否存在，如果存在，就不用管了。 答案就是Rank(root,x)-1，否則，我們就應該先插入x，然後執行Rank(root,x)-1，再刪除x，這樣耗時明顯增多，不過還是 能過。  

#include <iostream>  
#include <string.h>  
#include <stdlib.h>  
#include <stdio.h>  
  
using namespace std;  
  
struct Treap  
{  
    int size;  
    int key,fix;  
    Treap *ch[2];  
    Treap(int key)  
    {  
        size=1;  
        fix=rand();  
        this->key=key;  
        ch[0]=ch[1]=NULL;  
    }  
    int compare(int x) const  
    {  
        if(x==key) return -1;  
        return x<key? 0:1;  
    }  
    void Maintain()  
    {  
        size=1;  
        if(ch[0]!=NULL) size+=ch[0]->size;  
        if(ch[1]!=NULL) size+=ch[1]->size;  
    }  
};  
  
void Rotate(Treap* &t,int d)  
{  
    Treap *k=t->ch[d^1];  
    t->ch[d^1]=k->ch[d];  
    k->ch[d]=t;  
    t->Maintain();  //必須先維護t，再維護k，因為此時t是k的子節點  
    k->Maintain();  
    t=k;  
}  
  
void Insert(Treap* &t,int x)  
{  
    if(t==NULL) t=new Treap(x);  
    else  
    {  
        //int d=t->compare(x);   //如果值相等的元素只插入一個  
        int d=x < t->key ? 0:1;  //如果值相等的元素都插入  
        Insert(t->ch[d],x);  
        if(t->ch[d]->fix > t->fix)  
            Rotate(t,d^1);  
    }  
    t->Maintain();  
}  
  
//一般來說，在調用刪除函數之前要先用Find()函數判斷該元素是否存在  
void Delete(Treap* &t,int x)  
{  
    int d=t->compare(x);  
    if(d==-1)  
    {  
        Treap *tmp=t;  
        if(t->ch[0]==NULL)  
        {  
            t=t->ch[1];  
            delete tmp;  
            tmp=NULL;  
        }  
        else if(t->ch[1]==NULL)  
        {  
            t=t->ch[0];  
            delete tmp;  
            tmp=NULL;  
        }  
        else  
        {  
            int k=t->ch[0]->fix > t->ch[1]->fix ? 1:0;  
            Rotate(t,k);  
            Delete(t->ch[k],x);  
        }  
    }  
    else Delete(t->ch[d],x);  
    if(t!=NULL) t->Maintain();  
}  
  
bool Find(Treap *t,int x)  
{  
    while(t!=NULL)  
    {  
        int d=t->compare(x);  
        if(d==-1) return true;  
        t=t->ch[d];  
    }  
    return false;  
}  
  
int Kth(Treap *t,int k)  
{  
    if(t==NULL||k<=0||k>t->size)  
        return -1;  
    if(t->ch[0]==NULL&&k==1)  
        return t->key;  
    if(t->ch[0]==NULL)  
        return Kth(t->ch[1],k-1);  
    if(t->ch[0]->size>=k)  
        return Kth(t->ch[0],k);  
    if(t->ch[0]->size+1==k)  
        return t->key;  
    return Kth(t->ch[1],k-1-t->ch[0]->size);  
}  
  
int Rank(Treap *t,int x)  
{  
    int r;  
    if(t->ch[0]==NULL) r=0;  
    else  r=t->ch[0]->size;  
    if(x==t->key) return r+1;  
    if(x<t->key)  
        return Rank(t->ch[0],x);  
    return r+1+Rank(t->ch[1],x);  
}  
  
int Depth(Treap *t)  
{  
    if(t==NULL) return -1;  
    int l=Depth(t->ch[0]);  
    int r=Depth(t->ch[1]);  
    return l<r ? (r+1):(l+1);  
}  
  
void DeleteTreap(Treap* &t)  
{  
    if(t==NULL) return;  
    if(t->ch[0]!=NULL) DeleteTreap(t->ch[0]);  
    if(t->ch[1]!=NULL) DeleteTreap(t->ch[1]);  
    delete t;  
    t=NULL;  
}  
  
void Print(Treap *t)  
{  
    if(t==NULL) return;  
    Print(t->ch[0]);  
    cout<<t->key<<endl;  
    Print(t->ch[1]);  
}  
  
int main()  
{  
    int n,x;  
    char str[5];  
    scanf("%d",&n);  
    Treap *root=NULL;  
    while(n--)  
    {  
        scanf("%s%d",str,&x);  
        if(str[0]=='I')  
        {  
            if(!Find(root,x))  
                Insert(root,x);  
        }  
        else if(str[0]=='D')  
        {  
            if(Find(root,x))  
                Delete(root,x);  
        }  
        else if(str[0]=='K')  
        {  
            int tmp=Kth(root,x);  
            if(tmp==-1) puts("invalid");  
            else        printf("%d\n",tmp);  
        }  
        else  
        {  
            bool flag=1;  
            if(!Find(root,x))  
                Insert(root,x);  
            else  
                flag=0;  
            printf("%d\n",Rank(root,x)-1);  
            if(flag)  
                Delete(root,x);  
        }  
    }  
    DeleteTreap(root);  
    return 0;  
}