DDOSvoid's Blog

CF 1420C2 Pokémon Army (hard version)

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1420/problem/C2

Solution

容易发现，每次加的是递增序列的最后一项，减的递减序列的最后一项，即递增序列的第一项

然后我们可以这么写

1
2
3
a[0] = a[n + 1] = 0; 
for (int i = 0; i <= n; ++i)
    if (a[i] > a[i + 1]) ans += a[i] - a[i + 1];

然后这个东西显然支持交换

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
57
58
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cctype>
#define ll long long
#define db double
#define maxn 300010
#define cn const node
#define cQ const Queue
#define gc getchar
using namespace std;

int read() {
    int x = 0; char c = gc();
    while (!isdigit(c)) c = gc();
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return x;
}

int n, m, a[maxn];

ll ans;
inline void del(int k) {
    if (a[k] > a[k + 1]) ans -= a[k] - a[k + 1];
    if (a[k - 1] > a[k]) ans -= a[k - 1] - a[k];
}

inline void add(int k) {
    if (a[k] > a[k + 1]) ans += a[k] - a[k + 1];
    if (a[k - 1] > a[k]) ans += a[k - 1] - a[k];
}


void work() {
    cin >> n >> m; ans = 0; a[0] = a[n + 1] = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 0; i <= n; ++i) 
        if (a[i] > a[i + 1]) ans += a[i] - a[i + 1];
    cout << ans << endl; 
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        del(l); del(r); if (l == r - 1 && a[l] > a[r]) ans += a[l] - a[r]; 
        swap(a[l], a[r]);
        add(l); add(r); if (l == r - 1 && a[l] > a[r]) ans -= a[l] - a[r]; 
        cout << ans << endl; 
    }
} 

int main() {
    int T; cin >> T;
    while (T--) work();
    return 0;
}