Vexoben
Mar 2, 2019
题目链接：ZJOI2016 大森林
一道题调了一年，码力还是太弱了。
（刷新以获取数学公式）
题意
有棵树，每棵树初始有一个节点.设计一个数据结构，支持：
0、在第到棵树的生长节点下面挂一个孩子.如果这是第个0操作，那么孩子节点的编号为.初始每棵树的生长节点都是1.
1、将第到 棵树的生长节点置为.如果一棵树没有节点,那么不更改.
2、询问第棵树上点和点的距离.
数据范围:
题解
同时维护棵树的结构显然不现实.但是我们可以离线后求出每棵树最终的样子.显然在最终的树上进行查询还是在中间的树上查询不会影响答案.
对于每个1操作,我们建立一个虚点;对于每个操作,我们建立一个实点.一个实点对应的虚点是上一个建立的虚点(一开始的生长节点是,相当于插入了一个虚点)
从到遍历每棵树.每个实点和虚点都有一个生效的区间.当一个实点生效时,我们将它连接到它对应的虚点;当它失效时,cut这条边.当一个虚点生效时,将它连接到对应的实点上;当它失效时,将它连接到上一个虚点上.
可以这样考虑正确性:只要每个实点都在正确的位置上就可以了.它本身如果失效,那他没有任何连边.如果它和它连接的虚点都生效,显然是正确的.如果它生效,而它连接的虚点失效,它会随着虚点之间的边连到生效的最早的点上,从而保证了,将每个点的父亲连接到它第一个非虚点的祖先后,形成的树和原树相同.
需要注意的是,统计答案的时候不能直接求两点路径上实点的数目.因为如果LCA是虚点,它其实对应它第一个非虚点的祖先,从而导致少算了的贡献,求一下LCA特判即可.
LCT求LCA的方法:先,再,答案就是最后一次轻重边转换的位置,具体可以看代码的部分.
#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
namespace LCT {
int V, fa[N], val[N], sum[N], rev[N], ch[N][2];
int Nw(int v) {
++V;
val[V] = sum[V] = v;
return V;
}
int Isroot(int x) {
return (ch[fa[x]][0] != x) && (ch[fa[x]][1] != x);
}
int Get(int x) {
return (ch[fa[x]][1] == x);
}
inline void Pushup(int x) {
sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + val[x];
}
inline void Pushdown(int x) {
if (rev[x]) {
rev[x] = 0;
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
swap(ch[x][0], ch[x][1]);
}
}
void Rotate(int x) {
int y = fa[x], z = fa[y], k = Get(x);
fa[x] = z;
if (!Isroot(y)) ch[z][Get(y)] = x;
ch[y][k] = ch[x][k ^ 1];
fa[ch[x][k ^ 1]] = y;
ch[x][k ^ 1] = y;
fa[y] = x;
Pushup(y); Pushup(x);
}
void Splay(int x) {
static int top, st[N];
st[top = 1] = x;
for (int i = x; !Isroot(i); i = fa[i]) {
st[++top] = fa[i];
}
while (top) Pushdown(st[top--]);
for (; !Isroot(x); Rotate(x)) {
if (!Isroot(fa[x])) {
Get(x) == Get(fa[x]) ? Rotate(fa[x]) : Rotate(x);
}
}
}
int Access(int x) {
int i;
for (i = 0; x; i = x, x = fa[x]) {
Splay(x);
ch[x][1] = i;
Pushup(x);
}
return i;
}
void Evert(int x) {
Access(x); Splay(x); rev[x] ^= 1;
}
void Link(int x, int y) {
Evert(x); Access(y); Splay(y);
fa[x] = y;
}
void Cut(int x, int y) {
Evert(x); Access(y); Splay(y);
fa[x] = ch[y][0] = 0;
Pushup(y);
}
int Query(int x, int y) {
int ans = 0;
Evert(1);
Access(x); Splay(x);
ans += sum[x];
int lca = Access(y); Splay(y);
ans += sum[y];
Access(lca); Splay(lca);
ans -= 2 * sum[lca];
return ans;
}
}
void read(int &x) {
char c = getchar();
while (c < '0' || c > '9') c = getchar();
for (x = 0; c >= '0' && c <= '9'; c = getchar())
x = (x << 3) + (x << 1) + c - '0';
}
int q, n, m, rv, las, tot, L[N], R[N], num[N], ans[N];
struct ope {
int x, opt, ins, pre, pos, node;
bool operator < (const ope &b) const {
return pos < b.pos;
}
}a[N];
struct que {
int u, v, ord;
};
vector<que> vec[N];
int main() {
cin >> n >> m;
num[++rv] = LCT::Nw(1);
las = LCT::Nw(0);
LCT::Link(num[1], las);
L[1] = 1; R[1] = n;
for (int i = 1; i <= m; ++i) {
int opt, l, r, x;
read(opt);
if (opt == 0) {
read(l); read(r);
x = LCT::Nw(1);
num[++rv] = x;
L[rv] = l; R[rv] = r;
a[++tot] = (ope) {x, 0, 1, las, l};
a[++tot] = (ope) {x, 0, -1, las, r + 1};
}
if (opt == 1) {
read(l); read(r); read(x);
l = max(l, L[x]);
r = min(r, R[x]);
if (l <= r) {
int t = LCT::Nw(0);
a[++tot] = (ope) {num[x], 1, 1, las, l, t};
a[++tot] = (ope) {num[x], 1, -1, las, r + 1, t};
LCT::Link(t, las);
las = t;
}
}
if (opt == 2) {
read(x); read(l); read(r);
vec[x].push_back((que) {l, r, ++q});
}
}
sort(a + 1, a + tot + 1);
for (int i = 1, p = 1; i <= n; ++i) {
while (p <= tot && a[p].pos == i) {
if (a[p].opt == 0) {
if (a[p].ins == 1) {
LCT::Link(a[p].x, a[p].pre);
}
if (a[p].ins == -1) {
LCT::Cut(a[p].x, a[p].pre);
}
}
if (a[p].opt == 1) {
if (a[p].ins == 1) {
LCT::Cut(a[p].node, a[p].pre);
LCT::Link(a[p].node, a[p].x);
}
if (a[p].ins == -1) {
LCT::Cut(a[p].node, a[p].x);
LCT::Link(a[p].node, a[p].pre);
}
}
++p;
}
for (int j = 0; j < vec[i].size(); ++j) {
int x = vec[i][j].u, y = vec[i][j].v;
ans[vec[i][j].ord] = LCT::Query(num[x], num[y]);
}
}
for (int i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
}
return 0;
}