就是写替罪羊模版的。
有一件非常恐怖的事情，就是我在ins的时候判是否重建，第7个点就会跑13秒
然后删了就A了！！A了？？？
upd：我尝试把平衡因子改成0.5也能过，从0.5开始往上加复杂度就逐渐增加。
upd2：发现是递归版本的ins从下往上修改，所以从上往下修改问题就不大了。
upd3：发现现在还是从下往上修改，但是只改一次。有点玄学。
upd：感觉这个东西很不可用啊。。。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; const double alpha=0.75; struct node { int c,son[2],tot,siz,alive;//tot表示管理节点总数(纯属用来判重建)siz表示除去被删除的节点的总数，alive表示该点是否被删 }tr[210000];int root; int top,sta[210000];//用于回收空间 int Llen,L[110000];//得出暴力重建的子树的中序遍历 void gotravel(int x) { if(x==0)return ; gotravel(tr[x].son[0]); if(tr[x].alive==1)L[++Llen]=x; else sta[++top]=x; gotravel(tr[x].son[1]); } int build(int l,int r)//重建与值无关，只是改变树的形态 { if(l>r)return 0; if(l==r) { int x=L[l]; tr[x].son[0]=tr[x].son[1]=0; tr[x].tot=tr[x].siz=1; return x; } int mid=(l+r)/2; int x=L[mid]; tr[x].son[0]=build(l,mid-1); tr[x].son[1]=build(mid+1,r); int lc=tr[x].son[0],rc=tr[x].son[1]; tr[x].tot=tr[lc].tot+tr[rc].tot+1; tr[x].siz=tr[lc].siz+tr[rc].siz+1; return x; } void rebuild(int f,int x,int w) { Llen=0;gotravel(x); int tt=build(1,Llen); if(f!=0)tr[f].son[w]=tt; else root=tt; }//------------rebuild------------------ void add(int f,int d,int w) { int x=sta[top];top--; tr[x].c=d; tr[x].son[0]=tr[x].son[1]=0; tr[x].tot=tr[x].siz=1; tr[x].alive=1; if(f!=0)tr[f].son[w]=x; else root=x; } int tlen,tmp[110000]; void ins(int d) { if(root==0) { add(0,d,0); return ; } int x=root; tlen=0;tmp[0]=0;tmp[++tlen]=x; while(x!=0) { tr[x].tot++;tr[x].siz++; int lc=tr[x].son[0],rc=tr[x].son[1]; if(d<=tr[x].c) { if(lc==0){add(x,d,0);break;} else x=lc, tmp[++tlen]=x; } else { if(rc==0){add(x,d,1);break;} else x=rc, tmp[++tlen]=x; } } for(int i=tlen;i>=1;i--) { int x=tmp[i]; int lc=tr[x].son[0],rc=tr[x].son[1]; if( (double(tr[x].siz))*alpha > (double(max(tr[lc].siz,tr[rc].siz))) ) { int gf=tmp[i-1],goat=x,w; if(tr[gf].son[0]==goat)w=0; else w=1; rebuild(gf,goat,w); break; } } }//--------------------ins------------------- int findrank(int d) { int x=root,ret=1; while(x!=0) { if(d<=tr[x].c)x=tr[x].son[0]; else ret+=tr[tr[x].son[0]].siz+tr[x].alive, x=tr[x].son[1]; } return ret; } void del(int d) { int x=root,k=findrank(d); while(x!=0) { tr[x].siz--; int lc=tr[x].son[0],rc=tr[x].son[1]; if(tr[lc].siz+1==k&&tr[x].alive==1){tr[x].alive=0;break;} else if(k<=tr[lc].siz)x=lc; else k-=tr[lc].siz+tr[x].alive, x=rc; } if( (double(tr[root].tot))*alpha > (double(tr[root].siz)) )rebuild(0,root,0); }//--------------------del-------------------- //------------------simple--------------- int findmath(int k) { int x=root; while(x!=0) { int lc=tr[x].son[0],rc=tr[x].son[1]; if(tr[lc].siz+1==k&&tr[x].alive==1)return tr[x].c; else if(k<=tr[lc].siz)x=lc; else k-=tr[lc].siz+tr[x].alive, x=rc; } } //----------for the problem------------ int main() { freopen("ptszs.in","r",stdin); freopen("ptszs.out","w",stdout); int n,op,x; scanf("%d",&n); root=0; for(int i=205000;i>=1;i--)sta[++top]=i; for(int i=1;i<=n;i++) { scanf("%d%d",&op,&x); if(op==1)ins(x); else if(op==2)del(x); else if(op==3)printf("%d ",findrank(x)); else if(op==4)printf("%d ",findmath(x)); else if(op==5)printf("%d ",findmath(findrank(x)-1)); else if(op==6)printf("%d ",findmath(findrank(x+1))); } return 0; }