题解 CF571D 【Campus】
xht
2020-02-05 17:13:46
> [CF571D Campus](https://codeforces.com/contest/571/problem/D)
## 题意
- 有一个长度为 $n$ 的序列，初始全为 $0$。
- 有两类对下标的集合，初始时每一类各有 $n$ 个集合，编号为 $i$ 的集合里有下标 $i$。
- 一共有 $m$ 个操作，操作有五种：
1. `U x y` 将第一类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
2. `M x y` 将第二类编号为 $y$ 的集合合并到编号为 $x$ 的集合里。
3. `A x` 将第一类编号为 $x$ 的集合中的所有下标在序列中对应的数加上 $x$ 的集合大小。
4. `Z x` 将第二类编号为 $x$ 的集合中的所有下标在序列中对应的数设为 $0$。
5. `Q x` 询问序列中下标为 $x$ 的位置上的数。
- $n,m \le 5 \times 10^5$。
## 题解
如果我们能够利用 `M` 和 `Z` 操作求出对于每个询问的位置上次清零的时刻 $t$，那么这个询问的答案就应该是只保留 `U` 和 `A` 操作的情况下此时的值减去 $t$ 时刻的值。
那么我们要解决的问题可以分为两步：
1. 利用 `M` 和 `Z` 操作求出对于每个询问的位置上次清零的时刻 $t$。
2. 利用 `U` 和 `A` 操作求出对于每个询问的位置当前和时刻 $t$ 的值。
将询问离线后，建立 kruskal 重构树，那么这两步就分别相当于在 dfs 序上进行区间赋值和区间加，询问则相当于单点查询，线段树维护即可。
设 $n,m$ 同阶，时间复杂度为 $\mathcal O(n \log n)$。
## 代码
```cpp
const int N = 5e5 + 7;
int n, m, a[N];
char s[N], c[3];
vector<pi> q[N];
ll ans[N];
struct kruskal0 {
int f[N*2], l[N*2], r[N*2], num, tot;
vi e[N*2];
struct T {
int l, r, s;
} t[N*8];
inline void init() {
for (int i = 1; i <= n; i++) f[i] = i;
tot = n;
}
int get(int x) {
return x == f[x] ? x : (f[x] = get(f[x]));
}
inline int add(int x, int y) {
e[++tot].pb(x = get(x)), e[tot].pb(y = get(y));
return f[x] = f[y] = f[tot] = tot;
}
void dfs(int x) {
l[x] = ++num;
for (auto y : e[x]) dfs(y);
r[x] = num;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return;
build(ls, l, md), build(rs, md + 1, r);
}
inline void prework() {
for (int i = 1; i <= tot; i++) if (get(i) == i) dfs(i);
build(1, 1, tot);
}
inline void spd(int p) {
if (t[p].s) t[ls].s = t[rs].s = t[p].s, t[p].s = 0;
}
void set(int p, int l, int r, int x) {
if (t[p].l >= l && t[p].r <= r) return t[p].s = x, void();
spd(p);
if (l <= md) set(ls, l, r, x);
if (r > md) set(rs, l, r, x);
}
inline void set(int i) {
set(1, l[a[i]], r[a[i]], i);
}
int asks(int p, int x) {
if (t[p].l == t[p].r) return t[p].s;
spd(p);
return asks(x <= md ? ls : rs, x);
}
inline int asks(int i) {
return asks(1, l[a[i]]);
}
} t0;
struct kruskal1 {
int f[N*2], s[N*2], l[N*2], r[N*2], num, tot;
vi e[N*2];
struct T {
int l, r;
ll a;
} t[N*8];
inline void init() {
for (int i = 1; i <= n; i++) f[i] = i;
tot = n;
}
int get(int x) {
return x == f[x] ? x : (f[x] = get(f[x]));
}
inline int add(int x, int y) {
e[++tot].pb(x = get(x)), e[tot].pb(y = get(y));
return f[x] = f[y] = f[tot] = tot;
}
void dfs(int x) {
l[x] = ++num, s[x] = x <= n;
for (auto y : e[x]) dfs(y), s[x] += s[y];
r[x] = num;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return;
build(ls, l, md), build(rs, md + 1, r);
}
inline void prework() {
for (int i = 1; i <= tot; i++) if (get(i) == i) dfs(i);
build(1, 1, tot);
}
inline void spd(int p) {
if (t[p].a) t[ls].a += t[p].a, t[rs].a += t[p].a, t[p].a = 0;
}
void add(int p, int l, int r, int x) {
if (t[p].l >= l && t[p].r <= r) return t[p].a += x, void();
spd(p);
if (l <= md) add(ls, l, r, x);
if (r > md) add(rs, l, r, x);
}
inline void add(int x) {
add(1, l[x], r[x], s[x]);
}
ll aska(int p, int x) {
if (t[p].l == t[p].r) return t[p].a;
spd(p);
return aska(x <= md ? ls : rs, x);
}
inline ll aska(int x) {
return aska(1, l[x]);
}
} t1;
int main() {
rd(n), rd(m), t1.init(), t0.init();
for (int i = 1, x; i <= m; i++) {
rds(c, x), s[i] = c[1], rd(a[i]);
switch (s[i]) {
case 'U' : rd(x), a[i] = t1.add(a[i], x); break;
case 'M' : rd(x), a[i] = t0.add(a[i], x); break;
case 'A' : a[i] = t1.get(a[i]); break;
case 'Z' : a[i] = t0.get(a[i]); break;
}
}
t1.prework(), t0.prework();
for (int i = 1; i <= m; i++)
switch (s[i]) {
case 'Z' : t0.set(i); break;
case 'Q' : q[t0.asks(i)].pb(mp(a[i], i)); break;
}
for (int i = 1; i <= m; i++)
switch (s[i]) {
case 'A' : t1.add(a[i]); break;
case 'Z' : for (pi o : q[i]) ans[o.se] -= t1.aska(o.fi); break;
case 'Q' : ans[i] += t1.aska(a[i]); break;
}
for (int i = 1; i <= m; i++) if (s[i] == 'Q') print(ans[i]);
return 0;
}
```