题目大意：有$n(n\leqslant2\times10^5)$个序列，有$m(m\leqslant2\times10^5)$个操作，分三种：
1. $M\;x\;y：$把$x$所在的序列放在$y$所在序列之后
2. $D\;x：$把$x$所在的序列从它前面断开
3. $Q\;x\;y：$询问若$x,y$在同一序列中，它们之间的元素和
题解：平衡树，合并就正常合并，注意是把$x$放到$y$后，关于找$x$所在的序列，就记录每个节点的父亲，直接向上跳父亲就可以了，在分裂时注意维护父亲。
求元素的排名就看一下它是不是它父亲的右儿子，是的话把它兄弟的大小加上。
询问就记录一个区间和即可。
卡点：无
C++ Code：
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define maxn 200010 namespace Treap {
int pri[maxn], lc[maxn], rc[maxn], fa[maxn], sz[maxn], V[maxn];
long long S[maxn];
int ta, tb, tmp, res;
inline void nw(int pos, int x) {
pri[pos] = rand();
S[pos] = V[pos] = x;
lc[pos] = rc[pos] = fa[pos] = 0;
sz[pos] = 1;
}
inline int update(int rt) {
const int lc = Treap::lc[rt], rc = Treap::rc[rt];
if (lc) fa[lc] = rt;
if (rc) fa[rc] = rt;
sz[rt] = sz[lc] + sz[rc] + 1;
S[rt] = S[lc] + S[rc] + V[rt];
return rt;
}
void split(int rt, int k, int &x, int &y) {
if (!rt) x = y = 0;
else {
if (sz[lc[rt]] >= k) {
split(lc[rt], k, x, lc[rt]);
fa[x] = fa[rt] = 0;
y = update(rt);
} else {
split(rc[rt], k - sz[lc[rt]] - 1, rc[rt], y);
fa[rt] = fa[y] = 0;
x = update(rt);
}
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (pri[x] < pri[y]) { rc[x] = merge(rc[x], y); return update(x); }
else { lc[y] = merge(x, lc[y]); return update(y); }
}
inline int gtrnk(int x) {
res = sz[lc[x]] + 1;
while (x) {
if (rc[fa[x]] == x) res += sz[lc[fa[x]]] + 1;
x = fa[x];
}
return res;
}
inline int gtrt(int x) {
while (fa[x]) x = fa[x];
return x;
} inline void Merge(int x, int y) {
x = gtrt(x), y = gtrt(y);
if (x == y) return ;
merge(y, x);
}
inline void Split(int x) {
int rk = gtrnk(x); x = gtrt(x);
split(x, rk - 1, ta, tb);
}
inline void query(int x, int y) {
int root = gtrt(x);
if (root != gtrt(y)) {
puts("-1");
return ;
}
int rkx = gtrnk(x), rky = gtrnk(y);
if (rkx > rky) std::swap(rkx, rky);
split(root, rky, ta, tb);
split(ta, rkx - 1, ta, tmp);
printf("%lld\n", S[tmp]);
merge(ta, merge(tmp, tb));
}
} int n, m; int main() {
srand(20040826);
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
Treap::nw(i, x);
}
while (m --> 0) {
char op;
int x, y;
scanf("%1s%d", &op, &x);
switch (op) {
case 'M':
scanf("%d", &y);
Treap::Merge(x, y);
break;
case 'D':
Treap::Split(x);
break;
case 'Q':
scanf("%d", &y);
Treap::query(x, y);
}
}
return 0;
}