treap改了好长时间，erase写错了。。。
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int inf=<<;
int n,mn,root,delta,tot,leave;
int key[],cnt[],size[],p[];
int child[][];
void update(int x)
{
size[x]=size[child[x][]]+size[child[x][]]+cnt[x];
}
void rotate(int&x,int t)
{
int y=child[x][t];
child[x][t]=child[y][-t];
child[y][-t]=x;
update(x);
update(y);
x=y;
}
void insert(int&x,int k)
{
if(x)
{
if(key[x]==k)
{
cnt[x]++;
update(x);
return;
}
int t=key[x]<k;
insert(child[x][t],k);
if(p[x]<p[child[x][t]]) rotate(x,t);
update(x);
}
else
{
tot++;
x=tot;
p[x]=rand();
key[x]=k;
cnt[x]=;
update(x);
}
}
void erase(int&x,int k)
{
if(key[x]==k)
{
if(!child[x][]&&!child[x][])
{
x=;
return;
}
int t=p[child[x][]]>p[child[x][]];
rotate(x,t);
erase(child[x][t^],k);
} else erase(child[x][key[x]<k],k);
update(x);
}
void _erase(int x)
{
if(x==) return;
if(key[x]+delta<mn)
{
leave+=cnt[x];
if(key[child[x][]]+delta<mn)
{
leave+=size[child[x][]];
child[x][]=;
update(x);
}
_erase(child[x][]);
erase(root,key[x]);
}
_erase(child[x][]);
}
int find(int x,int k)
{
if(k<=size[child[x][]])
return find(child[x][],k);
k-=size[child[x][]]+cnt[x];
if(k<=)
return key[x];
return find(child[x][],k);
}
int main()
{
p[]=-inf;
scanf("%d%d",&n,&mn);
while(n--)
{
char s[]; int k; scanf("%s%d",s,&k);
if(s[]=='I')
{
if(k>=mn)
insert(root,k-delta);
}
if(s[]=='A')
{
delta+=k;
}
if(s[]=='S')
{
delta-=k;
_erase(root);
}
if(s[]=='F')
{
if(k>size[root]) printf("-1\n"); else
printf("%d\n",find(root,k)+delta);
}
}
printf("%d\n",leave);
return ;
}
splay
#include<cstdio>
#include<cstring>
using namespace std;
struct data
{
int fa,l,r,size,cnt,key;
}tree[];
int root,n,tot,ans;
int abs(int x)
{
return x>?x:-x;
}
void update(int x)
{
tree[x].size=tree[tree[x].l].size+tree[tree[x].r].size+tree[x].cnt;
}
void zig(int x)
{
int y=tree[x].fa;
int z=tree[x].r;
tree[y].l=z;
tree[z].fa=y;
tree[x].fa=tree[y].fa;
if(y==tree[tree[y].fa].l) tree[tree[y].fa].l=x;
else tree[tree[y].fa].r=x;
tree[x].r=y;
tree[y].fa=x;
update(x);
update(y);
}
void zag(int x)
{
int y=tree[x].fa;
int z=tree[x].l;
tree[y].r=z;
tree[z].fa=y;
tree[x].fa=tree[y].fa;
if(y==tree[tree[y].fa].l) tree[tree[y].fa].l=x;
else tree[tree[y].fa].r=x;
tree[x].l=y;
tree[y].fa=x;
update(x);
update(y);
}
void splay(int x)
{
if(!root)
{
root=x;
return;
}
while(tree[x].fa)
{
int y=tree[x].fa;
int z=tree[y].fa;
if(y==root)
{
if(x==tree[root].l) zig(x); else zag(x);
update(x);
break;
}
else if(y==tree[z].l&&x==tree[y].l) {zig(y); zig(x);}
else if(y==tree[z].r&&x==tree[y].r) {zag(y); zag(x);}
else if(y==tree[z].l&&x==tree[y].r) {zag(x); zig(x);}
else if(y==tree[z].r&&x==tree[y].l) {zig(x); zag(x);}
update(x);
}
root=x;
}
void insert(int x,int k)
{
if(tree[x].key==k)
{
tree[x].cnt++;
update(x);
splay(x);
}
else if(tree[x].key<k)
{
if(tree[x].r==)
{
++tot;
tree[tot].fa=x;
if(x) tree[x].r=tot;
tree[tot].key=k;
tree[tot].cnt=;
update(tot);
splay(tot);
return;
}
insert(tree[x].r,k);
update(x);
}
else if(tree[x].key>k)
{
if(tree[x].l==)
{
++tot;
tree[tot].fa=x;
if(x) tree[x].l=tot;
tree[tot].key=k;
tree[tot].cnt=;
update(tot);
splay(tot);
return;
}
insert(tree[x].l,k);
update(x);
}
}
int search(int x,int k)
{
if(tree[x].key==k) return x;
if(tree[x].key<k) return search(tree[x].r,k);
if(tree[x].key>k) return search(tree[x].l,k);
}
void findnxt(int x,int k,int pd)
{
if(x==) return;
if(pd==)
{
if(tree[x].key<k)
{
ans=x;
findnxt(tree[x].r,k,pd);
} else findnxt(tree[x].l,k,pd);
}
else
{
if(tree[x].key>k)
{
ans=x;
findnxt(tree[x].l,k,pd);
} else findnxt(tree[x].r,k,pd);
}
} void erase(int x)
{
findnxt(root,x,);
int pos=search(root,x);
splay(pos);
if(tree[pos].cnt>)
{
tree[pos].cnt--;
update(pos);
splay(pos);
return;
}
if(ans==)
{
root=tree[pos].r;
tree[root].fa=;
return;
}
if(tree[x].r==)
{
root=tree[x].l;
tree[root].fa=;
return;
}
// printf("%d %d\n",pos,pro);
tree[tree[pos].r].fa=ans;
tree[tree[pos].l].fa=;
root=tree[pos].l;
tree[ans].r=tree[pos].r;
splay(ans);
ans=;
}
int findrank(int x)
{
int pos=search(root,x);
splay(pos);
return tree[tree[pos].l].size+;
}
int find(int x,int k)
{
int y=tree[x].l;
int z=tree[x].r;
if(k<=tree[z].size) return find(z,k);
// printf("%d %d\n",tree[x].cnt,tree[z].size);
k-=tree[z].size+tree[x].cnt;
if(k<=) return tree[x].key;
return find(y,k);
}
int main()
{
scanf("%d",&n);
while(n--)
{
int opt,x; scanf("%d%d",&opt,&x);
if(opt==)
{
insert(root,x);
}
if(opt==)
{
erase(x);
}
if(opt==)
{
printf("%d\n",findrank(x));
}
if(opt==)
{
printf("%d\n",find(root,x));
}
if(opt==)
{
findnxt(root,x,opt);
printf("%d\n",tree[ans].key);
ans=;
}
if(opt==)
{
findnxt(root,x,opt);
printf("%d\n",tree[ans].key);
ans=;
}
}
return ;
}