CF571D Campus 题解

CF571D Campus

题意

• 有一个长度为 $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)$。

代码

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;
}