SB平衡树
#include<cstdio> #define MN 100000 #define L(x) c[x][0] #define R(x) c[x][1] #define rtf MN+1 #define rt L(rtf) #define INF 0x7FFFFFFF int fa[MN+5],c[MN+5][2],s[MN+5],p[MN+5],mk[MN+5],z[MN+5],tn; inline void mark(int x,int ad){z[x]+=ad;mk[x]+=ad;} inline void down(int x){if(mk[x])mark(L(x),mk[x]),mark(R(x),mk[x]),mk[x]=0;} inline void up(int x){s[x]=s[L(x)]+s[R(x)]+1;} inline int ran() { static int x=23333; return x^=x<<13,x^=x>>17,x^=x<<5; } void rotate(int x) { int f=fa[x],ff=fa[f],l=R(f)==x,r=l^1; fa[f]=x;fa[x]=ff;fa[c[x][r]]=f; c[ff][R(ff)==f]=x;c[f][l]=c[x][r];c[x][r]=f; up(f);up(x); } void ins(int f,int t,int x) { while(c[f][t])++s[f=c[f][t]],down(f),t=x>z[f]; fa[c[f][t]=++tn]=f;z[tn]=x;p[tn]=ran();s[tn]=1; while(p[tn]>p[fa[tn]])rotate(tn); } int find(int x,int k) { while(down(x),k) if(k<=s[L(x)])x=L(x); else if(k-=s[L(x)]+1)x=R(x); return x; } void del(int x) { fa[c[fa[x]][0]=R(x)]=fa[x]; while(x=fa[x])up(x); } int main() { int n,m,x,cnt=0;char t[MN+5]; p[rtf]=INF; scanf("%d%d",&n,&m); while(n--) { scanf("%s%d",t,&x); if(t[0]=='I')if(x>=m)ins(rtf,0,x); if(t[0]=='A')mark(rt,x); if(t[0]=='S'){mark(rt,-x);while(rt&&z[x=find(rt,1)]<m)del(x),++cnt;} if(t[0]=='F')printf("%d ",x>s[rt]?-1:z[find(rt,s[rt]-x+1)]); } printf("%d",cnt); }