P2357 守墓人

题目描述

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

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

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

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

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

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

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

  5. 求主墓碑的风水值

输入格式

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

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

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

1n,f2×105,答案不超过 64 位整数。

输出格式

输出会有若干行,对 45 的提问做出回答

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';
        }
    }
}