題目：http://www.spoj.com/problems/ORDERSET/

?

題意：給定n個(gè)操作，I,D,K,C,分別代表插入，刪除，找第K大元素，找小于x的元素個(gè)數(shù)。

?

分析：這里插入，刪除和找第K大元素很簡單，直接就是模版，但是這里找小于x的元素個(gè)數(shù)不好處理。

因?yàn)镽ank(Treap *t,int x)返回的是元素x在Treap中的排名，所以這里要求x在Treap一定是存在的，但是找小于x的元素個(gè)

數(shù)，這里的x不一定在Treap中。

?

后來我想到了一個(gè)方法，就是在查找之前，我們先查找x在Treap中是否存在，如果存在，就不用管了。

答案就是Rank(root,x)-1，否則，我們就應(yīng)該先插入x，然后執(zhí)行Rank(root,x)-1，再刪除x，這樣耗時(shí)明顯增多，不過還是

能過。

#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(); //必須先維護(hù)t，再維護(hù)k，因?yàn)榇藭r(shí)t是k的子節(jié)點(diǎn)k->Maintain();t=k; }void Insert(Treap* &t,int x) {if(t==NULL) t=new Treap(x);else{//int d=t->compare(x); //如果值相等的元素只插入一個(gè)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(); }//一般來說，在調(diào)用刪除函數(shù)之前要先用Find()函數(shù)判斷該元素是否存在 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);elseflag=0;printf("%d\n",Rank(root,x)-1);if(flag)Delete(root,x);}}DeleteTreap(root);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的SPOJ3273(Treap)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。