P2357 守墓人

题目描述

他把墓地分为主要墓碑和次要墓碑，主要墓碑只能有 $1$ 个，守墓人把他记为 $1$ 号，而次要墓碑有 $n-1$ 个，守墓人将之编号为 $2,3\dots n$，所以构成了一个有 $n$ 个墓碑的墓地。

而每个墓碑有一个初始的风水值，这些风水值决定了墓地的风水的好坏，所以守墓人需要经常来查询这些墓碑。

风水也不是不可变，除非遭遇特殊情况，已知在接下来的 $2147483647$ 年里，会有 $f$ 次灾难，守墓人会有几个操作：

1. 将 $[l,r]$ 这个区间所有的墓碑的风水值增加 $k$。

2. 将主墓碑的风水值增加 $k$

3. 将主墓碑的风水值减少 $k$

4. 统计 $[l,r]$ 这个区间所有的墓碑的风水值之和

5. 求主墓碑的风水值

输入格式

第一行，两个正整数 $n,f$ 表示共有 $n$ 块墓碑，并且在接下来的 $2147483647$年里，会有 $f$ 次世界末日

第二行，$n$ 个正整数，表示第 $i$ 块墓碑的风水值

接下来 $f$ 行，每行都会有一个针对世界末日的解决方案，如题所述，标记同题

$1\le n,f\le 2\times {10}^5$，答案不超过 64 位整数。

输出格式

输出会有若干行，对 $4$ 和 $5$ 的提问做出回答

Solution

直接套线段树板子即可。

#define int long long
#define lc u<<1
#define rc u<<1|1
int a[200010];
struct Tree { //线段树
    ll l, r, sum, add;
}tr[800010];

void pushup(ll u) { //上传
    tr[u].sum = tr[lc].sum + tr[rc].sum;
}
void pushdown(ll u) { //下传
    if (tr[u].add) {
        tr[lc].sum += tr[u].add * (tr[lc].r - tr[lc].l + 1);
        tr[rc].sum += tr[u].add * (tr[rc].r - tr[rc].l + 1);
        tr[lc].add += tr[u].add;
        tr[rc].add += tr[u].add;
        tr[u].add = 0;
    }
}
void build(ll u, ll l, ll r) { //建树
    tr[u] = {l,r,a[l],0};
    if (l == r) return;
    ll m = l + r >> 1;
    build(lc, l, m);
    build(rc, m + 1, r);
    pushup(u);
}
void change(ll u, ll l, ll r, ll k) { //区修
    if (l <= tr[u].l && tr[u].r <= r) {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].add += k;
        return;
    }
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= m) change(lc, l, r, k);
    if (r > m) change(rc, l, r, k);
    pushup(u);
}
ll query(ll u, ll l, ll r) { //区查
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    ll m = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    ll sum = 0;
    if (l <= m) sum += query(lc, l, r);
    if (r > m) sum += query(rc, l, r);
    return sum;
}
void solve() {
    int n, f;cin >> n >> f;
    for (int i = 1;i <= n;i++)cin >> a[i];
    int main = 0;
    build(1, 1, n);
    while (f--) {
        int op;cin >> op;
        if (op == 1) {
            int l, r, k;cin >> l >> r >> k;change(1, l, r, k);
        } else if (op == 2) {
            int k;cin >> k;
            main += k;
            // change(1, 1, 1, k);
        } else if (op == 3) {
            int k;cin >> k;
            main -= k;
            // change(1, 1, 1, -k);
        } else if (op == 4) {
            int l, r;cin >> l >> r;
            // cout << query(1, l, r) << "\n";
            cout << query(1, l, r) + (l == 1) * main << "\n";
        } else {
            cout << query(1, 1, 1) + main << '\n';
            // cout << query(1, 1, 1) << '\n';
        }
    }
}