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; }
补充:软件开发 , C++ ,