普通平衡树:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N=100010;
int read()
{
    int x=0,f=0,c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return f?-x:x; 
}

int sz[N],val[N],rnd[N],ch[N][2];
int n,cnt;
int root,rx,ry,rz;
void upd(int x){ sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;}

void split(int now,int k,int &x,int &y)
{
	if(!now){ x=y=0; return;}
	if(k>=val[now]) x=now,split( ch[now][1],k,ch[x][1],y);//错误1: >= 
	else y=now,split(ch[now][0],k,x,ch[y][0]);//错误2: 注意写法 
	upd(now);
}

int merge(int x,int y)
{
	if(!x||!y) return x+y;
	if(rnd[x]<rnd[y]){ ch[x][1]=merge(ch[x][1],y),upd(x); return x;}//注意要return 
	else { ch[y][0]=merge(x,ch[y][0]),upd(y); return y;}
}

int _new(int x)
{
	sz[++cnt]=1;val[cnt]=x; rnd[cnt]=rand();
	return cnt;
}
//错误点:要写上在那棵树上查找排名 
int findkth(int k,int rt)
{
	int now=rt;
	while(1)
	{
		int lsz=sz[ch[now][0]],rsz=sz[ch[now][1]];
		if(k==lsz+1) return now;
		else if(k>lsz) now=ch[now][1],k=k-(lsz+1);//错误3:这个地方要+1 
		else now=ch[now][0];//错误4: 用now 
	}
}

void print(int x)
{
	if(!x) return;
	print(ch[x][0]);
	cout<<val[x]<<' ';
	print(ch[x][1]);
}


int main()
{
	srand((unsigned)time(0));
	n=read();
	for(int i=1;i<=n;i++)
	{
		int opt=read(),x=read();
		if(opt==1)
		{
			split(root,x,rx,ry);
			root=merge( merge(rx,_new(x)),ry );
		}
		else if( opt==2)
		{
			split(root,x,rx,rz);
			split(rx,x-1,rx,ry);//错误点4:在rx为根的树上分裂 
			int t=merge(ch[ry][0],ch[ry][1]);
			root=merge( merge(rx,t),rz );
		}
		else if( opt==3)
		{
			split(root,x-1,rx,ry);//最初的rx与ry值没有影响 用来仅仅是暂时存储根节点
			printf("%d\n",sz[rx]+1);
			root=merge(rx,ry);
		}
		else if(opt==4) printf("%d\n",val[findkth(x,root)]);
		else if(opt==5)
		{
			split(root,x-1,rx,ry);
			printf("%d\n",val[findkth(sz[rx],rx)]);
			root=merge(rx,ry);
		}
		else if(opt==6)
		{
			split(root,x,rx,ry);
			printf("%d\n",val[findkth(1,ry)]);
			root=merge(rx,ry);
		}
	}
	return 0;
}