http://codeforces.com/contest/1420

C2. Pokémon Army (hard version)

 

题意：给定n的排列，要从数列中选出一个子序列，使得 ab1−ab2+ab3−ab4+…a_{b_1} - a_{b_2} + a_{b_3} - a_{b_4} + \dots 最大，多次操作，每次选择两个数交换，问交换前以及每次交换后这个最大值。

把数列画出来，一定是选择一段递减序列的头和尾，对每段递减序列都是如此。

把每次交换分成两步，del和ins，del删除这两个数的影响，ins插入这两个数。

需要注意的是当这两个数位置相邻时要特殊处理，因为删除时可能重复删除了它们相连的那条边，所以要把它加回来。同理插入时也可能重复加了这条边，要减去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define debug(x) cout << #x << ":\t" << x << endl;
#define ull unsigned ll
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 998244353;
int T;
int n, q;
int a[N], l, r;
ll ans;
void del(int p) {
	if (a[p] < a[p - 1])ans -= a[p - 1] - a[p];
	if (a[p] > a[p + 1])ans -= a[p] - a[p + 1];
}
void ins(int p) {
	if (a[p] < a[p - 1])ans += a[p - 1] - a[p];
	if (a[p] > a[p + 1])ans += a[p] - a[p + 1];
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &q);
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
		a[n + 1] = 0;
		int mx = 0;
		ans = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i] < a[i - 1] && a[i] < a[i + 1]) {
				ans += mx - a[i];
				mx = 0;
			}
			mx = max(mx, a[i]);
		}
		ans += mx;
		printf("%lld\n", ans);
		while (q--) {
			scanf("%d%d", &l, &r);
			del(l); 
			del(r);
			if (r == l + 1) {
				if (a[r] < a[l])ans += a[l] - a[r];
			}
			swap(a[l], a[r]);
			ins(l);
			ins(r);
			if (r == l + 1) {
				if (a[r] < a[l])ans -= a[l] - a[r];
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}