这题的确很神奇.
考虑每棵树是不会互相影响的, 所以我们可以将询问离线来做.
因为每次生长出来的节点编号都是一样且独一无二的,那么这些节点一定可以重复利用. 我们就只用建立一棵树来维护, 然后通过不断变化形态来解决问题.
因为我们询问的是路径长度, 所以询问点的祖先长了许多不存在的节点也无所谓.
因为在没有1操作的时间内, 所有的节点都是长到一起的. 那么我们每次转嫁节点比较麻烦, 所以我们考虑建立一个不存在的点来维护.
那么如果有一个1操作, 我们就新建一个虚点, 把期间所有的点转嫁到虚点上. 那么虚点影响的节点是([l, r]), 我们只要将该点在处理第l棵树的给过去，在r + 1处给回来。
（虚点之间是维护节点顺序的，所以在没有转嫁的时候就接到上一个虚点上面就可以了）
这样的话我们就直接把虚点的权值赋为0，实点赋为1即可。
关键是我们这里不能直接makeRoot， 或是说很麻烦。 因为我们这里有虚点，实点， 错综复杂的父子关系， 直接搞的话会打乱父子关系。
那么我们就用经典思路：
[Distance(u, v) = depth(u) + depth(v) - 2 * depth(LCA(u, v))
]
这样只要求出LCA就可以了, 那么我们直接返回Access操作的最后一个实链上的节点就可以了(先Access(u), 再返回Access(v)).
然后这一题目就完美的解决了.
总结一下:
-
如果我们要同时把大量的点一起接到别的点, 那么我们可以建立一条虚链(为了维护先后顺序, 如果没有这一点那就建散点也可以) 维护即可.(套路1)
-
我们在LCT上求LCA, 这在不MakeRoot的情况下直接返回Access的最后一个节点就可以了. 如果在含有MakeRoot的情况下可以采用标记Splay的方法.
-
在查询LCT一条路径上的信息时, 子树上接了别的东西是无所谓的.
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
char ch = getchar();
int x = 0, flag = 1;
for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
const int Maxn = 1e5 + 9, Maxm = 2e5 + 9;
template <int N> struct LCT {
struct node {
int val, sumVal, fa, ch[2];
}t[N];
int amount;
#define fa(x) t[(x)].fa
#define lc(x) t[(x)].ch[0]
#define rc(x) t[(x)].ch[1]
bool isroot(int u) {
return lc(fa(u)) != u && rc(fa(u)) != u;
}
void pushup(int u) {
t[u].sumVal = t[u].val + t[lc(u)].sumVal + t[rc(u)].sumVal;
}
void rotate(int u) {
int y = t[u].fa, z = t[y].fa, dir = t[y].ch[1] == u;
if(!isroot(y)) t[z].ch[t[z].ch[1] == y] = u; t[u].fa = z;
t[y].ch[dir] = t[u].ch[dir ^ 1]; t[t[u].ch[dir ^ 1]].fa = y;
t[u].ch[dir ^ 1] = y; t[y].fa = u;
pushup(y); pushup(u);
}
void splay(int u) {
while (!isroot(u)) {
int y = fa(u), z = fa(y);
if (!isroot(y))
(rc(y) == u) ^ (rc(z) == y) ? rotate(u) : rotate(y);
rotate(u);
}
pushup(u);
}
int access(int u) {
int y = 0;
for (; u; u = fa(y = u)) splay(u), t[u].ch[1] = y, pushup(u);
return y;
}
void cut(int u) { access(u); splay(u); t[lc(u)].fa = 0; t[u].ch[0] = 0; pushup(u); }
void link(int u, int v) { splay(u); t[u].fa = v; }
int newnode(int val, int pa = 0) { t[++amount].fa = pa; t[amount].val = val; t[amount].sumVal = val; return amount; }
#undef fa
#undef lc
#undef rc
};
LCT <Maxm + Maxn> T;
struct Quer {
int opt, Id, tar1, tar2;
//cut down Tar1 & link into Tar2. Id means in order, negitive: Cut/Link, positive: Query; opt: Which tree
};
bool cmp(Quer a, Quer b) { return a.opt < b.opt || (a.opt == b.opt && a.Id < b.Id); }
Quer s[Maxm * 3];
int n, m, lastVirtual, L[Maxm + Maxn], R[Maxm + Maxn], Tru[Maxm + Maxn], cntTru, tot;
bool isQuery[Maxn + Maxm];
int ans[Maxn + Maxm];
int query(int u) {
T.splay(u); return T.t[u].sumVal;
}
void init() {
n = read(), m = read();
T.newnode(1), lastVirtual = T.newnode(0, 1);
L[1] = 1; R[1] = n; Tru[1] = 1;
/**/cntTru = 1;
}
void solve() {
rep (i, 1, m) {
int opt = read();
if (opt == 0) {
int l = read(), r = read();
Tru[++cntTru] = T.newnode(1); L[cntTru] = l; R[cntTru] = r;
s[++tot] = (Quer){1, i - m, T.amount, lastVirtual};
}
if (opt == 1) {
int l = read(), r = read(), x = read();
l = max(l, L[x]), r = min(r, R[x]);
if (l > r) continue;
int u = T.newnode(0); T.link(u, lastVirtual);
s[++tot] = (Quer){l, i - m, u, Tru[x]};
s[++tot] = (Quer){r + 1, i - m, u, lastVirtual};
lastVirtual = u;
}
if (opt == 2) {
int x = read(), u = read(), v = read(); isQuery[i] = 1;
s[++tot] = (Quer){x, i, Tru[u], Tru[v]};
}
}
sort(s + 1, s + tot + 1, cmp);
int j = 1;
rep (i, 1, n)
for (; s[j].opt == i; ++j)
if (s[j].Id > 0) {
int target = s[j].Id;
T.access(s[j].tar1); ans[target] += query(s[j].tar1);
int LCA = T.access(s[j].tar2); ans[target] += query(s[j].tar2);
T.access(LCA); ans[target] -= 2 * query(LCA);
} else T.cut(s[j].tar1), T.link(s[j].tar1, s[j].tar2);
rep (i, 1, m)
if (isQuery[i]) printf("%d
", ans[i]);
}
int main() {
freopen("LOJ2092.in", "r", stdin);
freopen("LOJ2092.out", "w", stdout);
init();
solve();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return 0;
}