一道比LCT模板还要模板的模板(它甚至没有cut操作),主要借此题来阐述几个代码上的细节。
第一个是makelink函数。以下写法上对下错:
inline void makelink(int x,int y){
makeroot(x);
if(findroot(y)^x)t[x].f=y;
}
inline void makelink(int x,int y){
makeroot(x);
if(findroot(y)^x)t[y].f=x;
}
回答这个问题要回到LCT最基本的定义上来。LCT维护了一大堆的Splay,每一个Splay中的节点都会有一个父亲(根节点所在Splay的根除外),这父亲有两种情况,一种是Splay上的边,描述了一条实链的情况;另一种是树上的虚边,具体表现方式是这个Splay(也就是这条实链)的根有一个父亲,可怜的是父亲的左右孩子都不是它,这条链记录了这条实链中最浅节点在原树中的父亲。
总结一下,假如你要给一个Splay的根赋值父亲,就相当于给这棵Splay中最左边节点(原树中该实链最上面的节点)和某个节点连边。一定注意,这个活动的等效物是在原树中该实链最浅节点上连边,而非Splay根节点在原树中对应节点连边,一定要注意。所以要给一个根一个父亲,首先要保证它没有左孩子,这样才能做到所做即所得。
反应到代码中,由于x已经被makeroot了,可以保证它是它所在Splay中最浅的节点(这不废话吗),所以把x的fa设置为y是合理的,相反由于无法保证y是实链中最高的节点,所以把y的fa赋值为x是不合理的。所以才有了那样的写法。引以为戒。
另外一个就是rotate函数里一定要保证2+4的修改,即6组父子关系一定要弄到位。
#include<cstdio>
#define zczc
const int N=30010;
inline void read(int &wh){
wh=0;int f=1;char w=getchar();
while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
wh*=f;return;
}
inline void swap(int &s1,int &s2){
int s3=s1;s1=s2;s2=s3;return;
}
int m,n;
#define lc t[x].ch[0]
#define rc t[x].ch[1]
struct node{
int f,ch[2],data,sum;
bool lazy;
}t[N];
inline void pushdown(int x){
if(!t[x].lazy)return;t[x].lazy=false;
t[lc].lazy^=1,t[rc].lazy^=1,swap(lc,rc);
}
inline void pushup(int x){
t[x].sum=t[lc].sum+t[rc].sum+t[x].data;
}
inline bool check(int x){
int fa=t[x].f;
return t[fa].ch[0]==x||t[fa].ch[1]==x;
}
inline void rotate(int x){
int y=t[x].f;int z=t[y].f;bool kk=t[y].ch[1]==x;
if(check(y))t[z].ch[t[z].ch[1]==y]=x;
if(t[x].ch[!kk])t[t[x].ch[!kk]].f=y;
t[x].f=z;t[y].f=x;t[y].ch[kk]=t[x].ch[!kk];t[x].ch[!kk]=y;
pushup(y);pushup(x);return;
}
inline void pushdd(int x){
if(check(x))pushdd(t[x].f);
pushdown(x);
}
inline void splay(int x){
pushdd(x);
while(check(x)){
int y=t[x].f;int z=t[y].f;
if(check(y))(t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y);
rotate(x);
}
}
inline void access(int x){
for(int y=0;x;x=t[y=x].f){
splay(x);rc=y;
if(y)t[y].f=x;
pushup(x);
}
}
inline void makeroot(int x){
access(x);splay(x);
t[x].lazy^=1;
}
inline int findroot(int x){
access(x);splay(x);
while(t[x].ch[0])pushdown(x),x=lc;
return x;
}
inline void change(int x,int val){
access(x);splay(x);
t[x].data=val;pushup(x);
}
inline void makelink(int x,int y){
makeroot(x);
if(findroot(y)^x){printf("yes\n");t[x].f=y;}
else printf("no\n");
}
inline void work(int x,int y){
makeroot(x);
if(findroot(y)^x)printf("impossible\n");
else printf("%d\n",t[y].sum);
}
#undef lc
#undef rc
signed main(){
#ifdef zczc
freopen("in.txt","r",stdin);
#endif
read(m);char w[20];int s1,s2;
for(int i=1;i<=m;i++){
read(s1);t[i].data=t[i].sum=s1;
}
read(n);
for(int tt=1;tt<=n;tt++){
scanf("%s",w);read(s1);read(s2);
switch(w[0]){
case 'b':makelink(s1,s2);break;
case 'p':change(s1,s2);break;
case 'e':work(s1,s2);break;
}
}
return 0;
}