求助LCT
查看原帖
求助LCT
160839
Prean楼主2020/5/4 10:54

为什么这段代码CE了呀QwQ

Code:

#include<iostream>
const int M=2e5+5;
int n,m,k[M],s[M],f[M],st[M],lazy[M],chi[M][2];
bool get(int now)
{
	return chi[f[now]][0]==now||chi[f[now]][1]==now;
}
void filp(int now)
{
	std::swap(chi[now][0],chi[now][1]);lazy[now]^=1;
}
void undate(int now)
{
	s[now]=s[chi[now][0]]+s[chi[now][1]]+1;
}
void pushdown(int now)
{
	if(!lazy[now])return;lazy[now]=0;
	if(chi[now][0])filp(chi[now][0]);
	if(chi[now][1])filp(chi[now][1]);
}
void rotate(int x)
{
	int y=f[x],z=f[y],k=chi[y][1]==x,v=chi[x][!k];
	if(get(y))chi[z][chi[z][1]==y]=x;chi[x][!k]=y;chi[y][k]=v;
	if(v)f[v]=y;f[f[y]=x]=z;undate(y);
}
void Splay(int x)
{
	int y=x,top=0;st[++top]=y;
	while(get(y))st[++top]=y=f[y];
	while(top)pushdown(st[top--]);
	while(get(x))
	{
		top=f[y=f[x]];
		if(get(y))rotate((chi[y][0]==x)^(chi[top][0]==y)?y:x);
		rotate(x);
	}
	undate(x);
}
void Access(int x)
{
	for(register int y=0;x;x=f[y=x])Splay(x),chi[x][1]=y,undate(x);
}
int findroot(int x)
{
	Access(x);Splay(x);
	while(chi[x][0])pushdown(x),x=chi[x][0];
	Splay(x);return x;
}
void makeroot(int x)
{
	Access(x);Splay(x);filp(x);
}
void link(int x,int y)
{
	makeroot(x);if(findroot(y)!=x)f[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);
	if(findroot(y)==x&&f[y]==x&&!chi[y][0])f[y]=chi[x][1]=0,undate(x);
}
signed main(void)
{
	int i;
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	std::cin>>n;
	for(i=1;i<=n;++i)s[i]=1;
	for(i=1;i<=n;++i)
	{
		std::cin>>k[i];
		if(i+k[i]>n)link(i,n+1);
		else link(i,i+k[i]);
	}
	for(std::cin>>m;m;--m)
	{
		int x,y,opt;
		std::cin>>opt>>x;
		if(opt==1)
		{
			int ans=0;
			makeroot(x);x=n+1;Access(x);Splay(x);
			std::cout<<s[x]<<"\n";
		}
		if(opt==2)
		{
			std::cin>>y;
			if(x+k[x]>n)cut(x,n+1);
			else cut(x,x+k[x]);
			k[x]=y;
			if(x+k[x]>n)link(x,n+1);
			else link(x,x+k[x]);
		}
	}
}
2020/5/4 10:54
加载中...