【算法】平衡树(treap)
【题解】treap知识见数据结构
在POJ把语言从G++换成C++就过了……？？？
#include<cstdio> #include<algorithm> #include<ctime> using namespace std; const int maxn=50010; struct cyc{int num,w,rnd,l,r;}t[maxn*3]; int n,m,root,sz,s,tt,d[maxn]; void rr(int &tt)//右旋 { int k=t[tt].l; t[tt].l=t[k].r; t[k].r=tt; tt=k; } void lr(int &tt) { int k=t[tt].r; t[tt].r=t[k].l; t[k].l=tt; tt=k; } void insert(int &w,int x) { if(w==0) { w=++sz; t[w].num=x; t[w].w=1; t[w].rnd=rand(); return; } if(t[w].num==x){t[w].w++;return;}; if(x<t[w].num) { insert(t[w].l,x); if(t[t[w].l].rnd<t[w].rnd)rr(w); } if(x>t[w].num) { insert(t[w].r,x); if(t[t[w].r].rnd<t[w].rnd)lr(w); } } void del(int &w,int x) { if(t[w].num==x) { if(t[w].w>1) { t[w].w--; return; } if(t[w].l*t[w].r==0)w=t[w].l+t[w].r;//如果只有一颗子树，用这颗子树代替这个节点就可以删除了(没有子树则是用0代替之)。 else if(t[t[w].l].rnd<t[t[w].r].rnd) { rr(w); // del(t[w].r,x); del(w,x); } else { lr(w); // del(t[w].l,x); del(w,x); } } else if(t[w].num<x)del(t[w].r,x); else del(t[w].l,x); } void find(int w,int x) { if(w==0)return; if(t[w].num>=x&&t[w].num<tt)tt=t[w].num; if(t[w].num<=x&&t[w].num>s)s=t[w].num; if(t[w].num>x)find(t[w].l,x); if(t[w].num<x)find(t[w].r,x); } int main() { srand(time(0)); scanf("%d%d",&n,&m); for(int i=1,j=0;i<=m;i++) { // printf("[]"); char c=getchar();int x; c=getchar();//printf("[c=%c]",c); // while(c<'A'&&c>'Z')c=getchar(); if(c=='D') { scanf("%d",&x); insert(root,x); d[++j]=x; } if(c=='R')del(root,d[j--]); if(c=='Q') { s=0,tt=n+1; scanf("%d",&x); find(root,x); if(s==tt)printf("0 "); else printf("%d ",tt-s-1); } } return 0; }