洛谷P4847 银河英雄传说V2

传送门

题目背景

小H昨天看到了luogu P1196这一题，触发了他内心中对英雄的感慨/雾。可是无奈他不会这一题，只好去请教小W。在讲完那一题之后，小W灵机一动——不如改一下这道题吧。

于是，一个很水的签到题出现了。

题目描述

某dalao：把题目说简单一点，方便让我一分钟A掉！

于是小W只好把题意简化一下：

给定n个长度为1的序列，第i个序列中有一个元素，值为ai，接下来有三种操作：

M x y，表示把x所在的序列放到y所在的序列之后。如果x,y已经在同一个序列，则不进行操作。
D x，表示把x所在的序列中从x处断开，也就是把x及x之后的元素单独取出来作为一个序列。
Q x y，表示查询x到y之间（包括x和y）所有元素的值之和。如果x和y不在同一个序列之中，输出-1.
输入格式
第一行为两个数n,m，分别代表元素个数和操作次数。第二行有n个数，为ai。 接下来m行，每行包括三种情况：M x y，D x或Q x y，与题目描述对应。

输出格式

对于每一个Q x y，输出一个数，表示所有元素的值之和。

输入输出样例

输入 #1复制
5 10
57770 55352 18768 21847 79100
M 1 4
M 3 2
Q 5 2
M 3 4
M 3 5
M 4 4
M 3 1
D 1
Q 2 2
Q 2 1
输出 #1复制
-1
55352
113122
输入 #2复制
30 100
2193 75245 24438 95450 96514 84854 15292 9488 37488 940 52991 15190 64052 17398 80379 77861 88717 34751 16783 88345 27612 21748 79776 43058 35590 49064 45012 37206 70870 30643
M 18 26
M 28 27
M 25 4
M 12 22
M 26 15
M 3 1
M 20 20
M 7 21
M 18 29
M 21 26
M 29 10
M 27 23
M 30 28
M 22 10
M 13 21
M 1 23
M 25 9
M 29 27
M 23 25
M 11 12
M 1 4
M 26 14
M 26 9
D 4
M 16 8
M 16 20
M 4 27
M 9 20
M 11 1
M 19 8
Q 12 7
M 5 10
D 20
Q 29 2
Q 9 15
M 29 21
D 5
M 23 8
M 6 6
D 23
D 6
Q 4 8
D 21
Q 29 23
Q 19 4
M 21 21
M 20 25
M 27 29
D 2
Q 7 2
M 7 15
Q 11 18
D 26
Q 21 18
M 22 11
M 12 12
M 20 15
M 22 4
D 20
M 4 5
M 12 2
Q 27 20
M 30 2
M 28 9
M 20 11
M 10 21
M 12 24
Q 14 14
M 6 29
Q 13 18
Q 10 3
Q 23 3
D 4
M 27 13
M 6 23
M 7 14
Q 12 17
M 18 25
Q 2 19
D 3
D 9
Q 2 16
Q 3 8
Q 4 10
D 24
M 21 4
Q 17 15
Q 19 7
Q 1 24
Q 9 18
D 12
M 4 16
M 27 21
D 26
M 5 14
M 15 19
M 21 26
M 18 27
Q 21 8
Q 18 13
输出 #2复制
52230
-1
-1
254468
291078
112233
-1
231636
62363
-1
17398
178645
25378
219268
-1
419122
347453
-1
-1
-1
274542
-1
269126
-1
178645

说明/提示

（出题人非常良心地给了一个大一点的样例！）

样例1解释：

首先有5个序列（一个横排为一个序列），排列如下：

1
2
3
4
5
第一个操作将1放到4的后面，变成

2
3
4,1
5
第二个操作将3放到2后面，变成

2,3
4,1
5
然后查询第5个元素到第2个元素之间的和，由于不存在，输出-1；

将3所在的序列加到4所在的序列后面，变成

4,1,2,3
5
接下来变成了5,4,1,2,3，也就是所有元素都在1个序列了，因此接下来的两个合 并操作没有用了，然后把1之后的数字删除，变成：

1,2,3
5,4
查询2到2，输出2的值，也就是55352；

查询2到1，输出2+1的值，也就是113122.

为了避免某些乱搞（可能避免不了） ，前5个点按照传统方式计分，每个测试点10分；后五个点为subtask，必须全部通过才能得分，否则不得分。

对于所有数据，1<=x,y<=n，1<=ai<=10^9

上代码：

#include <bits/stdc++.h>
#define fq(i,a,b) for (int i = (a); i <= (b); i++)
#define fnq(i,a,b) for (int i = (a); i < (b); i++)
#define nfq(i,a,b) for (int i = (a); i >= (b); i--)
#define nfnq(i,a,b) for (int i = (a); i > (b); i--)
#define fqs(i,a,b,c) for (int i = (a); i <= (b); i += (c))
#define fnqs(i,a,b,c) for (int i = (a); i < (b); i += (c))
#define nfqs(i,a,b,c) for (int i = (a); i >= (b); i -= (c))
#define nfnqs(i,a,b,c) for (int i = (a); i > (b); i -= (c))
#define elif else if
using namespace std;
#define int long long

inline int rd () {
    
	int f = 1;
	char ch = getchar ();
	while (!isdigit (ch)) (ch == '-' ? (f = -1) : 0), ch = getchar ();
	int num = 0;
	while (isdigit (ch)) num = num * 10 + ch - '0', ch = getchar ();
	return num * f;
}
#define d rd ()

// 不支持虚子树有关的 LCT
const int maxn = 200200;
int ch[maxn][2], f[maxn], sum[maxn], val[maxn], tag[maxn];
#define ls(p) ch[p][0]
#define rs(p) ch[p][1]
void push_up (int p) {
    sum[p] = sum[ls (p)] + sum[rs (p)] + val[p];}
bool isroot (int p) {
    return p && ls (f[p]) != p && rs (f[p]) != p;}
void rev (int p) {
    swap (ls (p), rs (p)); tag[p] ^= 1;}
void push_down (int p) {
    if (tag[p]) {
    if (ls (p)) rev (ls (p)); if (rs (p)) rev (rs (p)); tag[p] = 0;}}
int which (int p) {
    return ch[f[p]][1] == p;}
void connect (int p, int fa, int w) {
    ch[fa][w] = p, f[p] = fa;}
void rotate (int p) {
    
	int fa = f[p], ffa = f[fa], wp = which (p), wfa = which (fa), pson = ch[p][wp ^ 1];
	if (!isroot (fa)) connect (p, ffa, wfa); else f[p] = ffa;
	connect (pson, fa, wp); connect (fa, p, wp ^ 1); push_up (fa); push_up (p);
}
void push_all (int p) {
    if (!isroot (p)) push_all (f[p]); push_down (p);}
void splay (int p) {
    
	push_all (p);
	for (int fa; fa = f[p], !isroot (p); rotate (p)) if (!isroot (fa))
		rotate (which (fa) == which (p) ? fa : p);
}
int find (int p, int w) {
    
	splay (p); push_down (p);
	while (ch[p][w]) push_down (ch[p][w]), p = ch[p][w];
	splay (p); return p; 
}
#define findroot(p) find(p, 0)
#define findleaf(p) find(p, 1)
void cut (int p) {
    splay (p); f[ls (p)] = 0; ls (p) = 0; push_up (p);}
int sm (int p) {
    splay (p); return sum[ls (p)] + val[p];}
signed main () {
    
	int n = d, m = d;
	fq (i, 1, n) val[i] = d;
	while (m--) {
    
		char op[10]; scanf ("%s", op);
		if (op[0] == 'M') {
    
			int x = d, y = d;
			// link 放 main 里面了
			if (findroot (x) != findroot (y))
				f[findroot (x)] = findleaf (y), rs (findleaf (y)) = findroot (x), push_up (findleaf (y));
		} elif (op[0] == 'D') cut (d); 
		else {
    
			int x = d, y = d;
			if (findroot (x) != findroot (y)) puts ("-1");
			else {
    
				int vx = sm (x), vy = sm (y);
				printf ("%lld\n", (vx > vy ? vx - vy + val[y] : vy - vx + val[x]));
			}
		}
	}
	return 0;
}