题解：P4847 银河英雄传说V2

比较典的一道数据结构。

考虑到没有奇怪的序列断开和追加操作变成了一个平衡树的模板题，可以 $O(\log n)$ 地解决。

那就不难想到用一颗平衡树森林来做，对于 $x$ 所在序列追加到 $y$ 的操作直接对两个序列找一下头。

相同忽略掉就行了。不同的话，我们还需要找到 $y$ 所在序列的尾。将 $x$ 的头放在 $y$ 所在序列尾的右子树即可。

接着，断开 $x$ 的操作无非就是将 $x$ 的前驱与 $x$ 双向断开。

这些操作在 Splay 上都是简单的。

所以，我们用一颗 Splay 森林做即可。

::::success[Code]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+5;
int ch[N][2], fa[N];
ll val[N], sum[N];
inline void pushup(int x) {
	sum[x] = val[x] + sum[ch[x][0]] + sum[ch[x][1]];
}
inline int get(int x) {
	return ch[fa[x]][1] == x;
}
inline void rotate(int x) {
	int y = fa[x], z = fa[y];
	int k = get(x);
	if (z)
		ch[z][get(y)] = x;
	ch[y][k] = ch[x][k ^ 1];
	if (ch[y][k])
		fa[ch[y][k]] = y;
	ch[x][k ^ 1] = y;
	fa[y] = x;
	fa[x] = z;
	pushup(y);
	pushup(x);
}
void splay(int x, int g = 0) {
	while (fa[x] != g) {
		int y = fa[x], z = fa[y];
		if (z != g) {
			if (get(x) == get(y))
				rotate(y);
			else
				rotate(x);
		}
		rotate(x);
	}
}
int find_root(int x) {
	splay(x);
	while (ch[x][0])
		x = ch[x][0];
	splay(x);
	return x;
}
int find_tail(int x) {
	splay(x);
	while (ch[x][1])
		x = ch[x][1];
	splay(x);
	return x;
}
void append(int x, int y) {
	x = find_root(x), y = find_root(y);
	if (x == y)
		return;
	int t = find_tail(y);
	ch[t][1] = x;
	fa[x] = t;
	pushup(t);
}
void cut(int x) {
	splay(x);
	if (ch[x][0]) {
		fa[ch[x][0]] = 0;
		ch[x][0] = 0;
		pushup(x);
	}
}
ll query(int x, int y) {
	if (find_root(x) != find_root(y)) 
		return -1;
	splay(x);
	if (x == y) 
		return val[x];
	splay(y, x);
	int k = get(y);
	return val[x] + val[y] + sum[ch[y][k ^ 1]];
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> val[i];
		pushup(i);
	}
	while (m--) {
		char op;
		cin >> op;
		if (op == 'M') {
			int x, y;
			cin >> x >> y;
			append(x, y);
		} else if (op == 'D') {
			int x;
			cin >> x;
			cut(x);
		} else {
			int x, y;
			cin >> x >> y;
			cout << query(x, y) << '\n';
		}
	}
	return 0;
}

::::