Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

joi2017ho_A フェーン現象 (Foehn Phenomena)

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

LuoGu: AT2442 フェーン現象 (Foehn Phenomena)

AtCoder: A - フェーン現象 (Foehn Phenomena)

按照题意维护差分数组即可，注意特判 $r = n$ 。

查看代码 
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
#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, q;
LL s, t, cur, A[N], d[N];
int main()
{
    scanf("%d%d%lld%lld", &n, &q, &s, &t);
    for (int i = 0; i <= n; i++)
        scanf("%lld", &A[i]);
    for (int i = 1; i <= n; i++)
        d[i] = A[i] - A[i - 1];
    for (int i = 1; i <= n; i++)
        if (d[i] > 0)
            cur -= d[i] * s;
        else if (d[i] < 0)
            cur += -d[i] * t;
    for (int l, r; q; q--)
    {
        LL x;
        scanf("%d%d%lld", &l, &r, &x);
        if (d[l] > 0)
            cur += d[l] * s;
        else if (d[l] < 0)
            cur -= -d[l] * t;
        d[l] += x;
        if (d[l] > 0)
            cur -= d[l] * s;
        else if (d[l] < 0)
            cur += -d[l] * t;
        if (r == n)
            goto print;
        if (d[r + 1] > 0)
            cur += d[r + 1] * s;
        else if (d[r + 1] < 0)
            cur -= -d[r + 1] * t;
        d[r + 1] -= x;
        if (d[r + 1] > 0)
            cur -= d[r + 1] * s;
        else if (d[r + 1] < 0)
            cur += -d[r + 1] * t;
    print:
        printf("%lld\n", cur);
    }
    return 0;
}