删除时不需要改size?数据水了?
查看原帖
删除时不需要改size?数据水了?
592895
y_kx_b楼主2022/4/10 11:59

第127行size[next]--,size[last]--;这句话删掉仍然可以过,是数据的锅还是这样写本来就没错?

求助

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define gc getchar
//return ~~(0^_^0);
using namespace std;
int read()
{
	int x=0;
	bool fh=1;
	char ch=gc();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')fh=0;
		ch=gc();
	}
	while(ch>='0'&&ch<='9')
		x=(x<<1)+(x<<3)+(ch^48),ch=gc();
	return fh?x:-x;
}
const int _=0,N=114514;
namespace SPLAY//https://www.shuzhiduo.com/A/xl56emaxJr/
{
	int ch[N][2],val[N],cnt[N],par[N],size[N],root=0,tot=0;
	#define fa par
	inline bool check(int x){return ch[par[x]][1]==x;}
	inline void pushup(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];}
	#define revolve spin 
	#define rotate revolve
	void spin(int x)
	{
		int y=par[x],z=par[y],k=check(x),w=ch[x][k^1];
		ch[y][k]=w,par[w]=y;
		ch[z][check(y)]=x,par[x]=z;
		ch[x][k^1]=y,par[y]=x;
		pushup(y),pushup(x);
	}
	void splay(int x,int goal=0)
	{
		while(par[x]!=goal)
		{
			int y=par[x];
			if(par[y]!=goal)
			{
				if(check(y)==check(x))spin(y);
				else revolve(x);
			}
			rotate(x);
		}
		if(!goal)root=x;
	}
	void find(int x)
	{
		if(!root)return;
		int cur=root;
		while(ch[cur][x>val[cur]]&&val[cur]!=x)
			cur=ch[cur][x>val[cur]];
		splay(cur);
	}
	void insert(int x)
	{
		int cur=root,p=0;
		while(cur&&val[cur]!=x)
		{
			p=cur;
			cur=ch[cur][x>val[cur]];
		}
		if(cur)//val[cur]==x
			cnt[cur]++;
		else
		{
			cur=++tot;//tot!=0
			if(p)ch[p][x>val[p]]=cur;
			ch[cur][0]=ch[cur][1]=0;
			val[cur]=x,par[cur]=p,cnt[cur]=size[cur]=1;
		}
		splay(cur);
	}
	inline int rnk(int x)
	{
		find(x);
		return size[ch[root][0]]+1;
	}
	int kth(int k)
	{
		int cur=root;
		while(1)
		{
			if(ch[cur][0]&&k<=size[ch[cur][0]])
				cur=ch[cur][0];
			else if(k>size[ch[cur][0]]+cnt[cur])
			{
				k-=size[ch[cur][0]]+cnt[cur];
				cur=ch[cur][1];
			}
			else return cur;
		}
	}
	int pre(int x)
	{
		find(x);
		if(val[root]<x)return root;
		int cur=ch[root][0];
		while(ch[cur][1])cur=ch[cur][1];
		return cur;
	}
	int suc(int x)
	{
		find(x);
		if(val[root]>x)return root;
		int cur=ch[root][1];
		while(ch[cur][0])cur=ch[cur][0];
		return cur;
	}
	void remove(int x)
	{
		int last=pre(x),next=suc(x);
		splay(last),splay(next,last);
		int tar=ch[next][0];
		if(val[tar]!=x)puts("UKE");
		if(cnt[tar]>1)
			 cnt[tar]--,
			 pushup(tar),
			 splay(tar);
		else ch[next][0]=0,
			 size[next]--,size[last]--;//?
	}
	void main()
	{
		insert(0xcfcfcfcf);//-808464433
		insert(0x3f3f3f3f);
		size[1]=size[2]=cnt[1]=cnt[2]=0;//不改也能过? 
		int p=read();
		while(p--)
		{
			int op=read(),x=read();
			switch(op)
			{
				case 1:insert(x);break;
				case 2:remove(x);break;
				case 3:printf("%d\n",rnk(x));break;
				case 4:printf("%d\n",val[kth(x)]);break;
				case 5:printf("%d\n",val[pre(x)]);break;
				case 6:printf("%d\n",val[suc(x)]);break;
			}
		}
	}
}
int main(){SPLAY::main();return~~(0^_^0);}
2022/4/10 11:59
加载中...