用last[x]表示对x进行的上一次操作的位置，vis[x]表示x是否在大楼内。
Splay维护'?'的位置。
若x要进楼：
1.若x已在楼内，则去找last[x]到i之间是否有'?'，若有，则可以把这个'?'当做是上一个x出楼，反之则 出现错误。
2.若x不在楼内，标记x在楼内。
若x要出楼：
1.若x在楼内，标记x不在楼内。
2.若x不在楼内，相同的去找last[x]到i之间是否有'?'。
#include<complex> #include<cstdio> using namespace std; const int N=5e5+7; int n,sz,rot,ans=-1; int key[N],fat[N],son[N][2],siz[N],last[N]; bool vis[N]; int qread() { int x=0; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='I')return 1; if(ch=='O')return 2; if(ch=='?')return 3; ch=getchar(); } while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } void Update(int rt) { siz[rt]=siz[son[rt][0]]+siz[son[rt][1]]+1; } void Rotate(int x,int &rt) { int a=fat[x],b=fat[a],l=son[a][1]==x,r=l^1; if(a==rt)rt=x; else son[b][son[b][1]==a]=x; fat[son[x][r]]=a;fat[a]=x;fat[x]=b; son[a][l]=son[x][r];son[x][r]=a; Update(a);Update(x); } inline void Splay(int x,int &rt) { while(x!=rt) { int a=fat[x],b=fat[a]; if(a!=rt) if((son[a][0]==x)^(son[b][0]==a)) Rotate(x,rt); else Rotate(a,rt); Rotate(x,rt); } } void Insert(int v,int k) { int fa=0; while(k && key[k]!=v) fa=k,k=son[k][key[k]<v]; k=++sz; key[k]=v;siz[k]=1;fat[k]=fa; if(fa)son[fa][key[fa]<v]=k; Splay(k,rot); } void Find(int x,int k) { while(son[k][key[k]<x] && x!=key[k]) k=son[k][key[k]<x]; Splay(k,rot); } void Delete(int x) { Find(x,rot); if(son[rot][0] && son[rot][1]) { int tmp=rot,k=son[rot][1]; rot=k; while(son[k][0])k=son[k][0]; siz[k]+=siz[son[tmp][0]]; fat[son[tmp][0]]=k;son[k][0]=son[tmp][0]; Splay(k,rot); } else rot=son[rot][0]+son[rot][1]; fat[rot]=0; } int GetNxt(int x) { Find(x,rot); if(key[rot]>x)return rot; int k=son[rot][1]; while(son[k][0])k=son[k][0]; return k; } int main() { scanf("%d",&n); int tmp,p,x; for(int i=1;i<=n;i++) { p=qread(); if(p==1) { x=qread(); if(vis[x]) { tmp=key[GetNxt(last[x])]; if(!tmp) { ans=i; break; } else Delete(tmp); } vis[x]=1; last[x]=i; } if(p==2) { x=qread(); if(!vis[x]) { tmp=key[GetNxt(last[x])]; if(!tmp) { ans=i; break; } else Delete(tmp); } vis[x]=0; last[x]=i; } if(p==3)Insert(i,rot); } printf("%d ",ans); return 0; }