题解 P2357 【守墓人】

xiaohuang · 2019-07-18 10:07:46 · 题解

更好的阅读体验

Solution

这题树状数组。（当然拦不住你用线段树/分块）

用c1[]来维护和，c2[]来维护积。

对于询问[x,y]区间，可以用query(y) - query(x - 1) + (x == 1) 主墓碑的风水值来求值，其中query(y) - query(x - 1)类似于前缀和，(x == 1) 主墓碑的风水值表示[x,y]区间包不包含主墓碑，如果包含则加上主墓碑单独维护的。

其中主墓碑需要单独维护。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

typedef long long LL;
const int MAXN = 500005;
int n, m, last;
LL first_value, c1[MAXN], c2[MAXN];
inline int lowbit(int x) {//树状数组专属操作
    return x & -x;
}
inline void update(int x, LL val) {//更新
    for (LL i = x; i <= n; i += lowbit(i)) {
        c1[i] += val;
        c2[i] += val * x;
    }
}
inline LL query(int x) {//查询
    LL ret = 0;
    for (LL i = x; i; i -= lowbit(i))
        ret += (x + 1) * c1[i] - c2[i];
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        update(i, x - last);
        last = x;
    }
    while (m--) {
        int opt, x, y;
        LL val;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%lld", &x, &y, &val);
            update(x, val);
            update(y + 1, -val);
        } else
        if (opt == 2) {
            scanf("%lld", &val);
            first_value += val;
        } else
        if (opt == 3) {
            scanf("%lld", &val);
            first_value -= val;
        } else
        if (opt == 4) {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(y) - query(x - 1) + (x == 1) * first_value);
        } else printf("%lld\n", query(1) + first_value);//统一维护的加单独维护的
    }
    return 0;
}