(其实今天好热啊?
题目大意:插入,删除,k小,前驱后继,数的排名。
splay和treap裸题...过几天补个treap的
splay:
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define which(x) (son[fa[x]][1]==x)
using namespace std;
const int extar[]={,-};
int fa[],count[],son[][],val[],data[];
int root,x,y,n,tot,xiugai;
void read(int &k)
{
k=;int f=;char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(c<=''&&c>='')k=k*+c-'',c=getchar();
k*=f;
}
void rotate(int x)
{
int f=fa[x];
bool k=which(x);
son[f][k]=son[x][!k];son[x][!k]=f;son[fa[f]][which(f)]=x;
if(son[f][k])fa[son[f][k]]=f;fa[x]=fa[f];fa[f]=x;
count[x]=count[f];
count[f]=count[son[f][]]+count[son[f][]]+val[f];
}
void splay(int x,int g)
{
while(fa[x]!=g)
{
int f=fa[x];
if(fa[f]==g)
{
rotate(x);
break;
}
if(which(x)^which(f))rotate(x);
else rotate(f);
rotate(x);
}
if(!g)root=x;
}
int search(int x,int y)
{
if(data[x]>y&&son[x][])return search(son[x][],y);
if(data[x]<y&&son[x][])return search(son[x][],y);
return x;
}
int ext(int x,int w)
{
int k=search(x,extar[w]);
splay(k,);
return data[k];
}
int pred(int w)
{
int k=search(root,w);
splay(k,);
if(data[k]<w)return data[k];
return ext(son[k][],);
}
int succ(int x)
{
int k=search(root,x);
splay(k,);
if(data[k]>x)return data[k];
return ext(son[k][],);
}
int rank(int x,int k)
{
if(k<=count[son[x][]])return rank(son[x][],k);
if(k<=(count[son[x][]]+val[x]))return x;
return rank(son[x][],k-count[son[x][]]-val[x]);
}
int findnum(int x)
{
int k=search(root,x);
splay(k,);
return count[son[k][]]+;
}
void insert(int &x,int w,int f)
{
if(!x)
{
x=++tot;
count[x]=val[x]=;
data[x]=w;
fa[x]=f;
xiugai=tot;
return;
}
if(data[x]==w)val[x]++,xiugai=x;
if(data[x]<w)insert(son[x][],w,x);
if(data[x]>w)insert(son[x][],w,x);
count[x]++;
}
void del(int w)
{
int k=search(root,w);
splay(k,);
if(data[k]==w)
{
if(val[k]>)val[k]--,count[k]--;
else
if(!son[k][])
{
root=son[k][];
fa[root]=fa[k]=son[k][]=count[k]=val[k]=data[k]=;
}
else
{
fa[son[k][]]=;ext(son[k][],);
son[root][]=son[k][];
if(son[k][])fa[son[k][]]=root;
count[root]+=count[son[k][]];
fa[k]=son[k][]=son[k][]=data[k]=val[k]=count[k]=;
}
}
}
int main()
{
read(n);
for(int i=;i<=n;i++)
{
read(x);read(y);
switch(x)
{
case :insert(root,y,);splay(xiugai,);root=xiugai;break;
case :del(y);break;
case :printf("%d\n",findnum(y));break;
case :printf("%d\n",data[rank(root,y)]);break;
case :printf("%d\n",pred(y));break;
case :printf("%d\n",succ(y));break;
default:break;
}
}
}