【算法】平衡树(treap)
【题解】treap知识见数据结构
在POJ把语言从G++换成C++就过了……？？？
#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int maxn=;
struct cyc{int num,w,rnd,l,r;}t[maxn*];
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==)
{
w=++sz;
t[w].num=x;
t[w].w=;
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>)
{
t[w].w--;
return;
}
if(t[w].l*t[w].r==)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==)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());
scanf("%d%d",&n,&m);
for(int i=,j=;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=,tt=n+;
scanf("%d",&x);
find(root,x);
if(s==tt)printf("0\n");
else printf("%d\n",tt-s-);
}
}
return ;
}