Record

最后一个点是一条链+反复查询极值rank。

然后我发现：

int get_rank(int v)
{
	int fak,k=root;
	int p=0;
	while(1)
	{
		if(!k)
		{
			if(!p)
				return 1;
			splay(p,0);
			fprintf(stderr,"[%d]\n",p==tree[fak].fa); // 全输出 "[1]"
			return tree[tree[p].son[0]].size+tree[p].tot+1;
		}
		if(tree[k].v<v&&(!p||tree[k].v>tree[p].v))
			p=k;
		fak=k;
		k=tree[k].son[tree[k].v<v];
	}
}

注意到此时 $fak$ 为叶子结点，splay $fak$ 后却还是一条链。怀疑 $splay$ 函数有误。

不过 $splay$ 和 $rotate$ 与这篇题解几乎完全相同。

给了大致方向，再给出完整代码：

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

#define N 100005

int q;
struct node
{
	int v,tot,size;
	int fa,son[2];
	node(){}
	node(int v):v(v),tot(1),size(1){}
} tree[N];
int root,idx;
void debug_node(int k){fprintf(stderr,"[%d: v=%d tot=%d size=%d fa=%d son[0]=%d son[1]=%d]\n",k,tree[k].v,tree[k].tot,tree[k].size,tree[k].fa,tree[k].son[0],tree[k].son[1]);}
void debug_tree(int k){if(!k)return;debug_tree(tree[k].son[0]);debug_node(k);debug_tree(tree[k].son[1]);}

void pushup(int k){tree[k].size=tree[tree[k].son[0]].size+tree[k].tot+tree[tree[k].son[1]].size;}

void rotate(int x)
{
	int y = tree[x].fa, z = tree[y].fa, chk = (x == tree[y].son[1]);
	tree[y].son[chk] = tree[x].son[chk ^ 1];
	if (tree[x].son[chk ^ 1]) tree[tree[x].son[chk ^ 1]].fa = y;
	tree[x].son[chk ^ 1] = y;
	tree[y].fa = x;
	tree[x].fa = z;
	if (z) tree[z].son[y == tree[z].son[1]] = x;
	pushup(y);pushup(x);
}

void splay(int k,int fa)
{
	if(!fa)
		root=k;
	while(tree[k].fa!=fa)
	{
		if(tree[tree[k].fa].fa==fa);
		else if((tree[tree[tree[k].fa].fa].son[1]==tree[k].fa)==(tree[tree[k].fa].son[1]==k))
			rotate(tree[k].fa);
		else
			rotate(k);
		rotate(k);
	}
}

void insert(int v)
{
	int fak=0,k=root;
	if(!root)
	{
		tree[root=++idx]=node(v);
		// splay(idx,0);
		return;
	}
	while(1)
	{
		if(tree[k].v==v)
		{
			splay(k,0);
			++tree[root].tot;
			pushup(root);
			return;
		}
		fak=k;
		k=tree[k].son[tree[k].v<v];
		if(!k)
		{
			tree[++idx]=node(v);
			tree[fak].son[tree[fak].v<v]=idx;
			tree[idx].fa=fak;
			pushup(fak);
			splay(idx,0);
			return;
		}
	}
}

void del(int v)
{
	int k=root;
	while(1)
	{
		if(tree[k].v==v)
		{
			splay(k,0);
			if(--tree[root].tot)
				pushup(root);
			else if(!tree[root].son[0])
				root=tree[root].son[1],
				tree[root].fa=0;
			else if(!tree[root].son[1])
				root=tree[root].son[0],
				tree[root].fa=0;
			else
			{
				int p=tree[root].son[0];
				while(tree[p].son[1])
					p=tree[p].son[1];
				int t=root;
				splay(p,0);
				tree[root].son[1]=tree[t].son[1];
				tree[tree[root].son[1]].fa=root;
				pushup(root);
			}
			return;
		}
		k=tree[k].son[tree[k].v<v];
	}
}

int get_rank(int v)
{
	int fak,k=root;
	int p=0;
	while(1)
	{
		if(!k)
		{
			if(!p)
				return 1;
			splay(p,0);
			fprintf(stderr,"[%d]\n",p==tree[fak].fa);
			return tree[tree[p].son[0]].size+tree[p].tot+1;
		}
		if(tree[k].v<v&&(!p||tree[k].v>tree[p].v))
			p=k;
		fak=k;
		k=tree[k].son[tree[k].v<v];
	}
}

int get_kth(int rank)
{
	// fputs(";;;;;;;\n",stderr);
	int k=root;
	while(1)
	{
		// fprintf(stderr,"[%d]\n",rank);
		// debug_node(k);
		if(tree[tree[k].son[0]].size+1<=rank&&rank<=tree[tree[k].son[0]].size+tree[k].tot)
			return tree[k].v;
		int t=rank;
		rank-=(tree[tree[k].son[0]].size+tree[k].tot)*(tree[tree[k].son[0]].size+1<rank);
		k=tree[k].son[tree[tree[k].son[0]].size+1<t];
	}
	// fputs(";;;;;;;\n",stderr);
}

int get_prev(int v)
{
	int k=root;
	int ans=-2e9;
	while(k)
	{
		if(tree[k].v==v)
		{
			int p=tree[k].son[0];
			while(tree[p].son[1])
				p=tree[p].son[1];
			return p?tree[p].v:ans;
		}
		if(tree[k].v<v)
			ans=max(ans,tree[k].v);
		k=tree[k].son[tree[k].v<v];
	}
	return ans;
}

int get_next(int v)
{
	int k=root;
	int ans=2e9;
	while(k)
	{
		if(tree[k].v==v)
		{
			int p=tree[k].son[1];
			while(tree[p].son[0])
				p=tree[p].son[0];
			return p?tree[p].v:ans;
		}
		if(tree[k].v>v)
			ans=min(ans,tree[k].v);
		k=tree[k].son[tree[k].v<v];
	}
	return ans;
}

signed main()
{
	freopen("P3369_14.in","r",stdin);
	// freopen("P3369_14.out","w",stdout);
	// freopen("P3369_14.out","w",stderr);
	freopen("P3369_14.err","w",stderr);
	fclose(stdout);
	// fclose(stderr);
	scanf("%d",&q);
	while(q--)
	{
		// fprintf(stderr,"%d\n",q);
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			int v;
			scanf("%d",&v);
			insert(v);
		}
		else if(op==2)
		{
			int v;
			scanf("%d",&v);
			del(v);
		}
		else if(op==3)
		{
			int v;
			scanf("%d",&v);
			printf("%d\n",get_rank(v));
		}
		else if(op==4)
		{
			int v;
			scanf("%d",&v);
			printf("%d\n",get_kth(v));
		}
		else if(op==5)
		{
			int v;
			scanf("%d",&v);
			printf("%d\n",get_prev(v));
		}
		else if(op==6)
		{
			int v;
			scanf("%d",&v);
			printf("%d\n",get_next(v));
		}
		// fprintf(stderr,"root=%d idx=%d\n",root,idx);
		// debug_tree(root);
		// fputs("-----------------\n",stderr);
	}
	return 0;
}

qwq