Splay求助!!!
查看原帖
Splay求助!!!
381600
K_srh楼主2022/7/12 00:23

大佬们帮本蒟蒻看一下吧, 样例输到最后一个就运行错误退出了 也不知道是啥问题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int root;
struct K{
	int ch[2];
	int cnt;
	int size;
	int fa;
	int val;	
}tree[N*4];
int tot=0;
void U(int x)
{
	tree[x].size=tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+tree[x].cnt;
}
void rotate(int x)
{
	int y=tree[x].fa;
	int z=tree[y].fa;
	int k=tree[y].ch[1]==x;
	tree[z].ch[tree[z].ch[1]==y]=x;
	tree[x].fa=z;
	tree[y].ch[k]=tree[x].ch[k^1];
	tree[tree[x].ch[k^1]].fa=y;
	tree[x].ch[k^1]=y;
	tree[y].fa=x;
	U(x);U(y);
}
void Splay(int x,int goal)
{
	while(tree[x].fa=goal)
	{
		int y=tree[x].fa;
		int z=tree[y].fa;
		if(z!=goal)(tree[z].ch[0]==y)^(tree[y].ch[0]==x)?rotate(x):rotate(y);
		rotate(x);
	}
	if(goal==0)root=x;
}
void find(int x)
{
	int u=root;
	if(!u)return;
	while(tree[x].ch[x>tree[u].val]&&x!=tree[u].val)u=tree[u].ch[x>tree[u].val];
	Splay(u,0);
}
void insert(int x)
{
	int u=root,fa=0;
	while(u&&tree[u].val!=x)
	{
		fa=u;
		u=tree[u].ch[x>tree[u].val];
	}
	if(u)tree[u].cnt++;
	else
	{
		u=++tot;
		if(fa)tree[fa].ch[x>tree[fa].val]=u;
		tree[u].ch[0]=tree[u].ch[1]=0;
		tree[tot].fa=fa;
		tree[tot].val=x;
		tree[tot].cnt=1;
		tree[tot].size=1;
	}
	Splay(u,0);
}
int Next(int x,int k)
{
	find(x);
	int u=root;
	if(tree[u].val>x&&k)return u;
	if(tree[u].val<x&&!k)return u;
	u=tree[u].ch[k];
	while(tree[u].ch[k^1])u=tree[u].ch[k^1];
	return u;
}
void Delete(int x)
{
	int last=Next(x,0);
	int next=Next(x,1);
	Splay(last,0);
	Splay(next,last);
	int del=tree[next].ch[0];
	if(tree[del].cnt>1)
	{
		tree[del].cnt--;
		Splay(del,0);
	}
	else tree[next].ch[0]=0;
}
int kth(int x)
{
	int u=root;
	if(tree[u].size<x);
	return 0;
	while(1)
	{
		int y=tree[u].ch[0];
		if(x>tree[y].size+tree[u].cnt)
		{
			x-=tree[y].size+tree[u].cnt;
			u=tree[u].ch[1];
		}
		else
		{
			if(tree[y].size>=x)u=y;
			else return tree[u].val;
		}
	}	
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int tmp,x;
		scanf("%d%d",&tmp,&x);
		if(tmp==1)insert(x);
		if(tmp==2)Delete(x);
		if(tmp==3)
		{
			find(x);
			printf("%d\n",tree[tree[root].ch[0]].size);
		}
		if(tmp==4)printf("%d\n",kth(x));
		if(tmp==5)printf("%d\n",Next(x,0));
		if(tmp==6)printf("%d\n",Next(x,1));
	}
	return 0;
}
2022/7/12 00:23
加载中...