题解 P3348 【[ZJOI2016]大森林】
FlashHu
2018-04-04 18:03:57
## 思路分析
最简单粗暴的想法，肯定是大力LCT，每个树都来一遍link之类的操作啦（T飞就不说了）
考虑如何优化算法。如果没有1操作，肯定每个树都长一样。有了1操作，就来仔细分析一下对不同树的影响。
假设有一个1操作形如$l\ r\ x$，那么从微观来看差异，我们只关注第l-1棵树和第l棵树。再假设以后都没有了0操作，那么我们可以认为，第l棵树是第l-1棵树把这个1操作以后嫁接在原来生长节点上的所有节点（以及所有子树）全部转而嫁接到x上。再看第r棵树和第r+1棵树，是不是可以认为又把这些子树嫁接回来了对吧？
注意到题目没有说在线，又因为1操作是有限的，只有两个端点，那么如果我们能够快速从一棵树转移到下一颗树，复杂度就能够保证了。
问题就在于，怎样把一堆子树的父亲全部转移。~~zcy太强辣，我什么ETT都不会~~。。。。。。
所以可能又要用一个虚点的套路。对于每个1操作建一个虚点，以后的0操作都连在最近建好的虚点上。这样每次整体嫁接的时候，直接把这个虚点断掉它原来的父亲，再link过去就大功告成啦！一开始默认所有虚点都在一起（表示默认生长节点从来没变过），把1操作拆成两个嫁接操作，再对所有操作以端点为第一关键字，原时间顺序为第二关键字排序，再从左到右一个个处理。
至于2操作，可以发现等一棵树全处理完再回答关于这棵树的所有询问是完全没有问题的。具体实现又怎么办？首先要设点权了，实点（0操作加的点）为1，虚点为0。然后就split？NoNoNo！第一，这个树是有根的（根为1），强行makeroot会破坏原先的父子关系；第二，两个点在LCT中的LCA可能是虚点！那又如何是好？又来一波树上差分，答案是$s[x]+s[y]-2*s[$LCT中的LCA$]$（~~貌似不太方便直接证明，自己举一些栗子yy就好啦qwq~~）
然后在LCT中如何求LCA呢？就是access(x)再接着access(y)，access(y)过程中最后一个跳到的虚边的父节点（在access完成后函数里的x会变成0，而y就是这个点）。熟悉LCT的各种性质应该是可以很轻松的知道这种方法。（关于性质方面[蒟蒻的LCT总结](http://www.cnblogs.com/flashhu/p/8324551.html)依旧希望路过的Dalao们指正qwq）
蛇皮压行卡常（懒得写fread了）巨丑无比的代码
~~不过变量名应该是很好懂的~~
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define R RG int
#define I inline
#define G ch=getchar()
#define lc c[x][0]
#define rc c[x][1]
#define qr(P,O,X,Y) qry[++q]=(QRY){P,O,X,Y}
using namespace std;
const int N=300009;
struct QRY{//封结构体，把嫁接和询问按顺序排序
int pos,ord,x,y;
I bool operator<(RG QRY a)const{
return pos<a.pos||(pos==a.pos&&ord<a.ord);
}
}qry[N];
int f[N],c[N][2],s[N],gl[N],gr[N],at[N],ans[N];
bool v[N];
I void in(R&x){
register char G;
while(ch<'-')G;
x=ch&15;G;
while(ch>'-')x*=10,x+=ch&15,G;
}
I bool nrt(R x){return c[f[x]][0]==x||c[f[x]][1]==x;}
I void up(R x){s[x]=s[lc]+s[rc]+v[x];}
I void rot(R x){
R y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
if(nrt(y))c[z][c[z][1]==y]=x;c[x][!k]=y;c[y][k]=w;
up(f[w]=y);f[y]=x;f[x]=z;
}
I void sp(R x){
for(R y;nrt(x);rot(x))
if(nrt(y=f[x]))rot((c[f[y]][0]==y)^(c[y][0]==x)?x:y);
up(x);
}
I int ac(R x){R y=0;while(x)sp(x),rc=y,up(y=x),x=f[x];return y;}
I void ct(R x){ac(x);sp(x);lc=f[lc]=0;up(x);}
I void lk(R x,R y){sp(x);f[x]=y;}//蒟蒻的LCT越写越丑了。。。
int main(){
R q=0,tot=0,n,m,p,real,aux,i,op,l,r,x,y;
in(n);in(m);
real=v[1]=s[1]=at[1]=gl[1]=1;gr[1]=n;
lk(p=aux=2,1);//一开始也要来一个虚点
for(i=1;i<=m;++i){
in(op);in(l);in(r);
if(op==0){//默认一开始全长在一起
lk(at[++real]=++p,aux);v[p]=s[p]=1;
gl[real]=l;gr[real]=r;
}//gl和gr方便下面把无用的区间去掉
else if(op==1){//有些区间连这个点都没长出来，直接取min，max
in(x);l=max(l,gl[x]);r=min(r,gr[x]);
if(l>r)continue;
lk(++p,aux);
qr(l,i-m,p,at[x]);qr(r+1,i-m,p,aux);//-m是为了把所有嫁接放到询问之前
aux=p;//更新生长节点位置
}
else in(x),qr(l,++tot,at[r],at[x]);
}
sort(qry+1,qry+q+1);
for(i=1;i<=q;++i){
if(qry[i].ord>0){
ac(x=qry[i].x);sp(x);r=s[x];
l=ac(y=qry[i].y);sp(y);r+=s[y];
ac(l);ans[qry[i].ord]=r-(s[l]<<1);//差分一下
}
else ct(qry[i].x),lk(qry[i].x,qry[i].y);
}
for(i=1;i<=tot;++i)printf("%d\n",ans[i]);
return 0;
}
```