刚学LCT,求助
查看原帖
刚学LCT,求助
160839
Prean楼主2020/5/1 17:02

第一个操作就RE了。。。而且还不带提示框,看了return value才判断是RE。。。求助QwQ

Code:

#include<iostream>
#include<cstdio>
#include<cctype>
const int M=1e5+5;
class Link_Cut_Tree
{
private:
	int s[M],f[M],val[M],lazy[M],chi[M][2];
	int cnt,st[M];
	int son(int);
	int get(int);
	void filp(int);
	void Splay(int);
	void rotate(int);
	void undate(int);
	void Access(int);
	int findroot(int);
	void makeroot(int);
	void pushdown(int);
	void split(int,int);
public:
	int Ask(int,int);
	void Add(int,int);
	void cut(int,int);
	void link(int,int);
	void new_node(int);
}LCT;
int Link_Cut_Tree::son(int now)
{
	return chi[f[now]][1]==now;
}
int Link_Cut_Tree::get(int now)
{
	return chi[f[now]][0]==now||chi[f[now]][1]==now;
}
void Link_Cut_Tree::filp(int now)
{
	std::swap(chi[now][0],chi[now][1]);lazy[now]^=1;
}
void Link_Cut_Tree::Splay(int x)
{
	int top=0,y=st[++top]=x;
	while(get(x))st[++top]=y=f[y];
	while(top)pushdown(st[top]--);
	while(get(x))
	{
		y=f[x];top=f[y];
		if(get(y))rotate(son(x)^son(y)?x:y);
		rotate(x);
	}
	undate(x);
}
void Link_Cut_Tree::rotate(int x)
{
	int y=f[x],z=f[y],k=son(x),v=chi[x][!k];
	if(get(y))chi[z][son(y)]=x;chi[x][!k]=y;chi[y][k]=v;
	if(v)f[v]=y;f[f[y]=x]=z;undate(y);
}
void Link_Cut_Tree::undate(int now)
{
	val[now]=val[chi[now][0]]^val[chi[now][1]]^s[now];
}
void Link_Cut_Tree::Access(int x)
{
	for(register int y=0;x;x=f[y=x])Splay(x),chi[x][1]=y,undate(x);
}
int Link_Cut_Tree::findroot(int x)
{
	Access(x);Splay(x);
	while(chi[x][0])pushdown(x),x=chi[x][0];
	Splay(x);return x;
}
void Link_Cut_Tree::makeroot(int x)
{
	Access(x);Splay(x);filp(x);
}
void Link_Cut_Tree::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 Link_Cut_Tree::split(int x,int y)
{
	makeroot(x);Access(y);Splay(y);
}
int Link_Cut_Tree::Ask(int x,int y)
{
	split(x,y);return val[x];
}
void Link_Cut_Tree::Add(int now,int value)
{
	val[now]=value;
}
void Link_Cut_Tree::link(int x,int y)
{
	split(x,y);if(findroot(y)!=x)f[x]=y;
}
void Link_Cut_Tree::cut(int x,int y)
{
	split(x,y);
	if(findroot(y)==x&&f[y]==x&&!chi[y][0])f[y]=chi[x][1]=0,undate(x);
}
void Link_Cut_Tree::new_node(int value)
{
	s[++cnt]=value;
}
inline int read()
{
	char s;int n=0;while(!isdigit(s=getchar()));
	while(n=n*10+(s^48),isdigit(s=getchar()));return n;
}
signed main(void)
{
	int n=read(),m=read();
	for(register int i=1;i<=n;++i)LCT.new_node(read());
	while(m--)
	{
		int opt=read(),x=read(),y=read();
		if(opt==0)printf("%d\n",LCT.Ask(x,y));
		if(opt==1)LCT.link(x,y);
		if(opt==2)LCT.cut(x,y);
		if(opt==3)LCT.Add(x,y);
	}
}

封装不要在意

2020/5/1 17:02
加载中...