record

$del$ 函数出现 $k=0$，初步判断为树形错误。

hack:

12
1 2701
1 3869
1 3869
1 4414
2 3869
2 3869
1 2198
1 3877
1 4078
1 3495
2 2701
2 3495

{没有输出}

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 100005

const double alpha=0.6827551;
// const double alpha=1;
int q;
struct node
{
	int v,size;
	bool mydeleted;
	int deleted;
	int lson,rson;
	node():v(0),size(0),mydeleted(0),deleted(0),lson(0),rson(0){}
	node(int v):v(v),size(1),mydeleted(0),deleted(0),lson(0),rson(0){}
} tree[N];
int a[N],lena;
int root,idx;

void pushup(int k)
{
	tree[k].size=tree[tree[k].lson].size+(!tree[k].mydeleted)+tree[tree[k].rson].size;
	tree[k].deleted=tree[tree[k].lson].deleted+tree[k].mydeleted+tree[tree[k].rson].deleted;
}

void dfs(int k)
{
	if(!k)
		return;
	dfs(tree[k].lson);
	if(!tree[k].mydeleted)
		a[++lena]=k;
	dfs(tree[k].rson);
}

int rebuild(int l,int r)
{
	if(l>r)
		return 0;
	int mid=l+r>>1;
	tree[a[mid]].lson=rebuild(l,mid-1);
	tree[a[mid]].rson=rebuild(mid+1,r);
	pushup(a[mid]);
	return a[mid];
}

void mkbalance(int &k)
{
	if(alpha*tree[k].size>(double)max(tree[k].deleted,max(tree[tree[k].lson].size,tree[tree[k].rson].size)))
		return;
	lena=0;
	dfs(k);
	k=rebuild(1,lena);
}

void insert(int &k,int v)
{
	if(!k)
	{
		tree[k=++idx]=node(v);
		return;
	}
	if(v<=tree[k].v)
		insert(tree[k].lson,v);
	else
		insert(tree[k].rson,v);
	pushup(k);
	mkbalance(k);
}

void del(int &k,int v)
{
	if(!tree[k].mydeleted&&tree[k].v==v)
		tree[k].mydeleted=1;
	else if(v<=tree[k].v)
		del(tree[k].lson,v);
	else
		del(tree[k].rson,v);
	pushup(k);
	mkbalance(k);
}

bool find(int k,int v)
{
	if(!k)
		return 0;
	if(tree[k].v==v)
		return 1;
	if(v<tree[k].v)
		return find(tree[k].lson,v);
	return find(tree[k].rson,v);
}

int get_rank(int k,int v)
{
	if(!k)
		return 0;
	if(!tree[k].mydeleted&&tree[k].v==v)
		return find(tree[k].lson,v)?get_rank(tree[k].lson,v):tree[tree[k].lson].size+1;
	if(v<=tree[k].v)
		return get_rank(tree[k].lson,v);
	return tree[tree[k].lson].size+(!tree[k].mydeleted)+get_rank(tree[k].rson,v);
}

int get_kth(int k,int rank)
{
	if(!tree[k].mydeleted&&tree[tree[k].lson].size+1==rank)
		return tree[k].v;
	if(rank<=tree[tree[k].lson].size+(!tree[k].mydeleted))
		return get_kth(tree[k].lson,rank);
	return get_kth(tree[k].rson,rank-tree[tree[k].lson].size-(!tree[k].mydeleted));
}
	
signed main()
{
	freopen("P3369_9.in","r",stdin);
	freopen("P3369_9.out","w",stdout);
	// // freopen("P3369_7.out","w",stderr);
	// // freopen("P3369_7.err","w",stderr);
	// // fclose(stdout);
	// fclose(stderr);
	scanf("%d",&q);
	while(q--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int v;
			scanf("%d",&v);
			insert(root,v);
		}
		else if(op==2)
		{
			int v;
			scanf("%d\n",&v);
			del(root,v);
		}
		else if(op==3)
		{
			int v;
			scanf("%d",&v);
			bool t=find(root,v);
			if(!t)
				insert(root,v);
			printf("%d\n",get_rank(root,v));
			if(!t)
				del(root,v);
		}
		else if(op==4)
		{
			int rank;
			scanf("%d",&rank);
			printf("%d\n",get_kth(root,rank));
		}
		else if(op==5)
		{
			int v;
			scanf("%d",&v);
			bool t=find(root,v);
			if(!t)
				insert(root,v);
			printf("%d\n",get_kth(root,get_rank(root,v)-1));
			if(!t)
				del(root,v);
		}
		else
		{
			int v;
			scanf("%d",&v);
			bool t=find(root,v);
			if(!t)
				insert(root,v);
			printf("%d\n",get_kth(root,get_rank(root,v)+1));
			if(!t)
				del(root,v);
		}
	}
	return 0;
}