思路：
set+线段树；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxtree maxn<<2
int val[maxtree],tag[maxtree],L[maxtree],R[maxtree],mid[maxtree];
int op[maxn],ki[maxn],bi[maxn],cnt,size,n,ch[maxn][],f[maxn],root;
set<int>Set;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void build(int now,int l,int r)
{
L[now]=l,R[now]=r;if(l==r) return;mid[now]=l+r>>;
build(now<<,l,mid[now]),build(now<<|,mid[now]+,r);
}
inline void pushdown(int now)
{
val[now<<]+=tag[now],tag[now<<]+=tag[now];
val[now<<|]+=tag[now],tag[now<<|]+=tag[now];
tag[now]=;
}
void add(int now,int l,int r)
{
if(L[now]>=l&&R[now]<=r)
{
val[now]++,tag[now]++;
return;
}
if(tag[now]!=) pushdown(now);
if(l<=mid[now]) add(now<<,l,r);
if(r>mid[now]) add(now<<|,l,r);
}
void Minus(int now,int l,int r)
{
if(L[now]>=l&&R[now]<=r)
{
val[now]--,tag[now]--;
return;
}
if(tag[now]!=) pushdown(now);
if(l<=mid[now]) Minus(now<<,l,r);
if(r>mid[now]) Minus(now<<|,l,r);
}
int get(int to)
{
int l=,r=size,now=;
while(l!=r)
{
if(tag[now]!=) pushdown(now);
if(to<=mid[now]) r=mid[now],now=now<<;
else l=mid[now]+,now=now<<|;
}
return val[now];
}
void era(int to,int justval)
{
int l=,r=size,now=;
while(l!=r)
{
if(tag[now]!=) pushdown(now);
if(to<=mid[now]) r=mid[now],now=now<<;
else l=mid[now]+,now=now<<|;
}
val[now]=justval;
}
int main()
{
freopen("data.txt","r",stdin);
in(n);
for(int i=;i<=n;i++)
{
in(op[i]);
if(op[i]==) in(ki[i]),bi[++cnt]=ki[i];
}
sort(bi+,bi+cnt+),size=unique(bi+,bi+cnt+)-bi-,build(,,size);
int l,r,x,fa,cost;set<int>::iterator it,it_;
for(int i=;i<=n;i++)
{
if(op[i]==)
{
x=lower_bound(bi+,bi+size+,ki[i])-bi;
l=,r=,it=it_=Set.insert(x).first;
if(it!=Set.begin()) l=*(--it);
if(x!=*Set.rbegin()) r=*(++it_);
if(!l&&!r) root=x,cost=;
else if(l&&ch[l][]==) ch[l][]=x,f[x]=l,cost=get(l)+;
else if(r&&ch[r][]==) ch[r][]=x,f[x]=r,cost=get(r)+;
printf("%d\n",cost),era(x,cost);
}
if(op[i]==||op[i]==)
{
it=Set.begin(),x=*it;
if(x!=root)
{
printf("%d\n",get(x));
if(ch[x][]) Minus(,x+,f[x]-),ch[f[x]][]=ch[x][],f[ch[x][]]=f[x];
else ch[f[x]][]=;
ch[x][]=root,f[root]=x,f[x]=,root=x;
add(,,size),era(x,);
}
else printf("1\n");
if(op[i]==) root=ch[root][],f[root]=,Minus(,,size),Set.erase(it);
}
if(op[i]==||op[i]==)
{
it=Set.end(),x=*(--it);
if(x!=root)
{
printf("%d\n",get(x));
if(ch[x][]) Minus(,f[x]+,x-),ch[f[x]][]=ch[x][],f[ch[x][]]=f[x];
else ch[f[x]][]=;
ch[x][]=root,f[root]=x,f[x]=,root=x;
add(,,size),era(x,);
}
else printf("1\n");
if(op[i]==) root=ch[root][],f[root]=,Minus(,,size),Set.erase(it);
}
}
return ;
}