@description@
小 Y 家里有一个大森林，里面有 n 棵树，编号从 1 到 n。一开始这些树都只是树苗，只有一个节点，标号为 1。这些树都有一个特殊的节点，我们称之为生长节点，这些节点有生长出子节点的能力。小 Y 掌握了一种魔法，能让第 l 棵树到第 r 棵树的生长节点长出一个子节点。同时她还能修改第 l 棵树到第 r 棵树的生长节点。她告诉了你她使用魔法的记录，你能不能管理她家的森林，并且回答她的询问呢？
输入格式
第一行包含两个正整数 ，表示共有 n 棵树和 m 个操作。
接下来 m 行，每行包含若干非负整数表示一个操作，操作格式为：
0 l r 表示将第 l 棵树到第 r 棵树的生长节点下面长出一个子节点，子节点的标号为上一个 0 号操作叶子标号加 1（例如，第一个 0 号操作产生的子节点标号为 2）， l 到 r 之间的树长出的节点标号都相同。保证 1<=l<=r<=n 。
1 l r x 表示将第 l 棵树到第 r 棵树的生长节点改到标号为 x 的节点。对于 i (l<=i<=r) 这棵树，如果标号 x 的点不在其中，那么这个操作对该树不产生影响。保证 1<=l<=r<=n ， x 不超过当前所有树中节点最大的标号。
2 x u v 询问第 x 棵树中节点 u 到节点 v 点的距离，也就是在第 x 棵树中从节点 u 和节点 v 的最短路上边的数量。保证 1<=x<=n，这棵树中节点 u 和节点 v 存在。
输出格式
输出包括若干行，按顺序对于每个小 Y 的询问输出答案
样例输入
5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3
样例输出
1
2
数据范围与提示
N <= 10^5, M <= 2*10^5。
@solution@
对于每个 1 操作 l r x，我们发现它能影响到的树就是含有点 x 的树。而含有点 x 的树对应了一个 0 操作 l' r'。
则它能产生影响的树实际上只有 [l, r] 与 [l', r'] 的交集，可以发现这个也是一个区间。
因此，我们可以把 1 操作变成 “将某个区间内所有树的生长结点改成 x”，并且保证该区间都存在 x 这个结点。
然后我们再来看 0 操作。因为 1 操作（变化过后的）与 2 操作都保证了结点的存在性，那么假如我们加入一些不存在的结点，也不会影响答案。
因此 0 操作给定的区间 [l, r] 就没有什么用了。我们就可以视作所有树都长了这样一个结点出来。
对于 2 操作，我们的解决方法是：先维护出这棵树长什么样子，然后查询。
我们可以将 n 棵树看成 1 棵树的 n 个时刻，则每个 1 操作相当于在第 l 个时刻初插入一个操作，在第 r 个时刻末删除一个操作。
然后，对于每个 1 操作我们都建立 1 个虚点，第 i 个虚点连向第 i 次 1 操作到第 i+1 次 1 操作之间的 0 操作加入的实点（因为这些点在任意时刻都是在同一个父亲下的）。
假如第 i 个虚点连向第 j 个虚点，则我们理解为第 i 个虚点所管的实点与第 j 个虚点所管的实点在同一个父亲下。
假如第 i 个虚点连向一个实点 x，则我们理解为第 i 个虚点所管的实点的父亲为 x。
初始时所有操作都未执行，那么每个 1 操作对应的虚点向前一个虚点连边；第一个虚点连向结点 1。
每次插入一个 1 操作，就把这个 1 操作对应的虚点 i 连向实点 x；每次删除时，把这个 1 操作对应的虚点 i 连回第 i-1 个虚点。
查询不能直接查询两点之间的路径上的实点数量，需要对 lca 是实点还是虚点进行分类。
不过有一个替代方案：记 f(x) 表示 x 到根的实点数量，则直接查 f(u) + f(v) - 2*f( lca(u, v) ) 即可。
至于为什么，还是需要对 lca 是实点还是虚点进行分类。
@accepted code@
#include<vector>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
const int MAXM = 200000;
struct link_cut_tree{
struct node{
int rev;
int siz, key;
node *ch[2], *fa;
}pl[MAXM + 5], *ncnt, *NIL;
link_cut_tree() {
ncnt = NIL = &pl[0];
NIL->fa = NIL->ch[0] = NIL->ch[1] = NIL;
NIL->siz = NIL->key = 0;
}
void maintain(node *x) {
if( x != NIL ) {
swap(x->ch[0], x->ch[1]);
x->rev ^= 1;
}
}
void pushup(node *x) {x->siz = x->ch[0]->siz + x->ch[1]->siz + x->key;}
void pushdown(node *x) {
if( x->rev )
maintain(x->ch[0]), maintain(x->ch[1]), x->rev = 0;
}
node *newnode(int k) {
node *p = (++ncnt);
p->fa = p->ch[0] = p->ch[1] = NIL;
p->siz = p->key = k;
return p;
}
bool is_root(node *x) {
return x->fa->ch[0] != x && x->fa->ch[1] != x;
}
void set_child(node *x, node *y, int d) {
if( x != NIL ) x->ch[d] = y;
if( y != NIL ) y->fa = x;
}
void rotate(node *x) {
node *y = x->fa; int d = (y->ch[1] == x);
pushdown(y), pushdown(x);
if( is_root(y) ) x->fa = y->fa;
else set_child(y->fa, x, y->fa->ch[1] == y);
set_child(y, x->ch[!d], d);
set_child(x, y, !d);
pushup(y);
}
void splay(node *x) {
pushdown(x);
while( !is_root(x) ) {
node *y = x->fa;
if( is_root(y) )
rotate(x);
else {
node *z = y->fa;
if( (z->ch[1] == y) == (y->ch[1] == x) )
rotate(y);
else rotate(x);
rotate(x);
}
}
pushup(x);
}
void access(node *x) {
node *y = NIL;
while( x != NIL ) {
splay(x);
x->ch[1] = y;
pushup(x);
y = x, x = x->fa;
}
}
void make_root(node *x) {
access(x), splay(x), maintain(x);
}
void link(node *x, node *y) {
make_root(x), x->fa = y;
}
void cut(node *x, node *y) {
make_root(x), access(y), splay(y);
x->fa = NIL, y->ch[0] = y->ch[1] = NIL;
pushup(y);
}
node *lca(node *x, node *y) {
access(x), access(y), splay(x);
if( x->fa == NIL ) return x;
else return x->fa;
}
int query(node *x, node *y) {
access(x), splay(x); int p = x->siz;
access(y), splay(y); int q = y->siz;
node *l = lca(x, y);
access(l), splay(l); int r = l->siz;
return p + q - 2*r;
}
}T;
struct modify{link_cut_tree::node *a, *b, *c;}tmp;
struct node{int id, u, v;}tmp2;
vector<modify>mdf[MAXM + 5];
vector<node>qry[MAXM + 5];
link_cut_tree::node *nd0[MAXM + 5], *nd1[MAXM + 5];
int le[MAXM + 5], ri[MAXM + 5];
int cnt0, cnt1, cnt2;
int ans[MAXM + 5];
int main() {
int n, m; scanf("%d%d", &n, &m);
nd0[cnt0 = 1] = nd1[cnt1 = 1] = T.newnode(0);
le[1] = 1, ri[1] = n;
for(int i=1;i<=m;i++) {
int op; scanf("%d", &op);
if( op == 0 ) {
cnt0++; scanf("%d%d", &le[cnt0], &ri[cnt0]);
nd0[cnt0] = T.newnode(1);
T.link(nd0[cnt0], nd1[cnt1]);
}
else if( op == 1 ) {
int l, r, x; scanf("%d%d%d", &l, &r, &x);
l = max(l, le[x]), r = min(r, ri[x]);
if( l > r ) continue;
nd1[++cnt1] = T.newnode(0);
tmp.a = nd1[cnt1], tmp.b = nd1[cnt1-1], tmp.c = nd0[x], mdf[l].push_back(tmp);
tmp.a = nd1[cnt1], tmp.b = nd0[x], tmp.c = nd1[cnt1-1], mdf[r + 1].push_back(tmp);
T.link(nd1[cnt1], nd1[cnt1-1]);
}
else {
int x, u, v; scanf("%d%d%d", &x, &u, &v);
tmp2.id = (++cnt2), tmp2.u = u, tmp2.v = v, qry[x].push_back(tmp2);
}
}
for(int i=1;i<=n;i++) {
for(int j=0;j<mdf[i].size();j++)
T.cut(mdf[i][j].a, mdf[i][j].b), T.link(mdf[i][j].a, mdf[i][j].c);
for(int j=0;j<qry[i].size();j++)
T.make_root(nd0[1]), ans[qry[i][j].id] = T.query(nd0[qry[i][j].u], nd0[qry[i][j].v]);
}
for(int i=1;i<=cnt2;i++)
printf("%d
", ans[i]);
}
@details@
ZJOI 的题都是神仙题 * 3。
实现起来倒是很顺畅，基本上都是模板。主要是理解。