发现Splay有两个锅之后改了能够正常运行了,但是输出有点儿问题。。。求鞭尸QwQ
Code:
#include<iostream>
#include<cstdio>
#include<cctype>
const int M=1e5+5;
inline int read()
{
char s;int n=0;while(!isdigit(s=getchar()));
while(n=n*10+(s^48),isdigit(s=getchar()));return n;
}
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:
void build(int);
int Ask(int,int);
void Add(int,int);
void cut(int,int);
void link(int,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[chi[now][0]]^=1;lazy[chi[now][1]]^=1;
}
void Link_Cut_Tree::Splay(int x)
{
int top=0,y=st[++top]=x;
while(get(y))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])filp(now),lazy[now]=0;
}
void Link_Cut_Tree::split(int x,int y)
{
makeroot(x);Access(y);Splay(y);
}
void Link_Cut_Tree::build(int n)
{
for(register int i=1;i<=n;++i)s[i]=read();
}
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);
}
signed main(void)
{
int n=read(),m=read();LCT.build(n);
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);
}
}