splay的一些事情
查看原帖
splay的一些事情
182101
逆天峰王者楼主2020/5/2 08:13

请问这种写法的splay不加入边界INF和-INF,就会又wrong,又T,请问大佬原因?
刚学splay,希望大佬指点!在此谢过!

#include<bits/stdc++.h>
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define getc(a) scanf("%s",a+1)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e6+10;
int n,m,last,root,tot,ans;
struct wy
{
	int v,f,ch[2],sum,rec;
	#define v(x) t[x].v
	#define f(x) t[x].f
	#define sum(x) t[x].sum
	#define rec(x) t[x].rec
	#define ch(x,y) t[x].ch[y]
}t[N];
inline int read()
{
	int x=0,ff=1;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*ff;
}

inline void updata(int x) {sum(x)=sum(ch(x,0))+sum(ch(x,1))+rec(x);}

inline int random(int n){return (ll)rand()*rand()%n;}

inline void retato(int x)
{
	int y=f(x),z=f(y),k=ch(y,1)==x;
	ch(z,ch(z,1)==y)=x;f(x)=z;
	ch(y,k)=ch(x,k^1);f(ch(x,k^1))=y;
	ch(x,k^1)=y;f(y)=x;	
	updata(y);updata(x);
}

inline void splay(int x,int goal)
{
	while(f(x)!=goal)
	{
		int y=f(x),z=f(y);
		if(z!=goal) (ch(z,0)==y)^(ch(y,0)==x)?retato(x):retato(y);
		retato(x);
	}	
	if(goal==0) root=x;
}

inline int newpoint(int x,int fa)
{
	f(++tot)=fa;v(tot)=x;sum(tot)=rec(tot)=1;
	return tot;	
}

inline void insert(int x)
{
	int now=root;
	if(!now) {root=newpoint(x,0);return;}	
	while(1)
	{
		sum(now)++;
		if(v(now)==x) {rec(now)++;splay(now,0);return;}
		int next=x>v(now);
		if(!ch(now,next))
		{
			int p=newpoint(x,now);
			ch(now,next)=p;
			splay(p,0);return;
		}
		now=ch(now,next);
	}
}

inline void find(int x)
{
	int now=root;
	if(!now) return;
	while(v(now)!=x&&ch(now,x>v(now))) now=ch(now,x>v(now));
	splay(now,0);
}

inline int Next(int x,int op)
{
	find(x);
	int now=root;
	if(v(now)>x&&op) return now;
	if(v(now)<x&&!op) return now;
	now=ch(now,op);
	while(ch(now,op^1)) now=ch(now,op^1);
	return now;
} 

inline void delet(int x)
{
	int last=Next(x,0),next=Next(x,1);
	splay(last,0);splay(next,last);
	int now=ch(next,0);
	if(rec(now)>1) rec(now)--,splay(now,0);
	else ch(next,0)=0;
} 

inline int Kth(int x)
{
	int now=root;
	while(1)
	{
		int y=ch(now,0);
		if(x>sum(y)+rec(now)) 
		{
			x-=sum(y)+rec(now);
			now=ch(now,1);
		}
		else if(sum(y)>=x) now=ch(now,0);
		else
		{
			splay(now,0);
			return v(now);
		}
	}
}

int main()
{
	//freopen("1.in","r",stdin);
	get(n);get(m);
	insert(INF*2);insert(-INF*2);
	rep(i,1,n) 
	{
		int get(x);
		insert(x);
	}
	rep(i,1,m)
	{
		int get(opt),get(x);
		x^=last;
		if(opt==1) insert(x);
		else if(opt==2) delet(x);	
		else if(opt==3)
		{
			find(x);
			last=sum(ch(root,0));
			if(v(root)<x) last+=rec(root);
			ans^=last;
		}
		else if(opt==4) last=Kth(x+1),ans^=last; 
		else if(opt==5) last=v(Next(x,0)),ans^=last;
		else if(opt==6) last=v(Next(x,1)),ans^=last;
	}
	put(ans);
	return 0;
}
2020/5/2 08:13
加载中...