题解 | 2023第一场多校

Almost Correct

https://ac.nowcoder.com/acm/contest/57355/A

C题

（补题，思路源自于出题人题解）

单独考虑某一个位置 $p$ 受到的影响。

对于操作1，假设对位置 $p$ 总共增加了 $c$ 。

对于操作2，无论能不能减，每次都让位置 $p$ 减去 $k$ 。

那么显然对于操作2，多减了很多次 $k$ ，就要想办法找出这个次数。

假设位置 $p$ 变化过程是 $c_0, c_1, c_2, ...c_m$ ， $m$ 代表题目中的操作次数。

那么多减了 $\lceil \frac{-min(c_i)}{k} \rceil$ 次 $k$ 。(出题人题解的结论，不过证明太数学了，看不懂。)

个人理解：多减的情况肯定是某一个 $c_i$ 小于 $0$ ，才存在多减。（如果能减 $k$ 这么多，减完肯定大于等于 $0$ ）

我们只要关注最小的 $c_i$ ，只有这次是多减的。其它小于 $0$ 的 $c_i$ 不用管。

（因为对于 $x< y, 0\lt c_x\le c_y$ ，是递增的， $c_y$ 不起作用； $x\gt y, 0\lt c_x\le c_y$ ，是递减的，可以把 $c_y$ 产生的作用算到到 $c_x$ 的头上。）

找到最小的 $c_i$ ，位置 $p$ 明显就是多减了负的 $c_i$ 这么多，除以 $k$ 上取整就是多减的次数。

有了结论后，用线段树从位置 $1$ 不断维护到 $n$ ，维护当前位置所有 $c_i$ 。

对于第 $i$ 个操作：

如果是操作1，区间 $[L,R]$ 加 $x$ ，就是在位置 $L$ 维护线段树时，将线段树的 $i$ 到 $m$ 加上 $x$ ；在位置 $R+1$ 维护线段树时，将线段树的 $i$ 到 $m$ 减去 $x$ 。（差分的思想）

如果是操作2，区间 $[L,R]$ 减 $k$ ，就是在位置 $L$ 维护线段树时，将线段树的 $i$ 到 $m$ 减去 $k$ ；在位置 $R+1$ 维护线段树时，将线段树的 $i$ 到 $m$ 加上 $k$ 。

因为要找 ${min(c_i)}$ 和区间加，线段树搞一个最小值和区间加的懒标记就行了。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;

#define lson (k << 1)
#define rson (k << 1 | 1)

const int N = 3 + 1e6;
const int M = 3 + 2e5;

struct TreeNode {
    int l, r;
    LL minv, lazy;
} tr[M * 4];

vector<tuple<int, int, int>> ve[N];
int n, m, k;

void up(int k) {
    tr[k].minv = min(tr[lson].minv, tr[rson].minv);
}

void down(int k) {
    if (tr[k].lazy) {
        tr[lson].minv += tr[k].lazy;
        tr[rson].minv += tr[k].lazy;
        tr[lson].lazy += tr[k].lazy;
        tr[rson].lazy += tr[k].lazy;
        tr[k].lazy = 0;
    }
}

void build(int k, int l, int r) {
    tr[k].l = l;
    tr[k].r = r;
    if (l == r) {
        return;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

void update(int k, int l, int r, LL v) {
    if (l <= tr[k].l && tr[k].r <= r) {
        tr[k].minv += v;
        tr[k].lazy += v;
        return;
    }
    down(k);
    int mid = tr[k].l + tr[k].r >> 1;
    if (l <= mid) {
        update(lson, l, r, v);
    }
    if (r > mid) {
        update(rson, l, r, v);
    }
    up(k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
        int op, l, r, x;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> x;
            ve[l].push_back({1, i, x});
            ve[r + 1].push_back({1, i, -x});
        } else {
            ve[l].push_back({2, i, -k});
            ve[r + 1].push_back({2, i, k});
        }
    }
    build(1, 1, m);

    LL ans = 0;
    int d = 0; // 维护减的次数(不考虑多减情况)

    for (int i = 1; i <= n; ++i) {
        for (auto [op, t, v] : ve[i]) {
            update(1, t, m, v);
            if (op == 2) {
                if (v < 0) {
                    ++d;
                } else {
                    --d;
                }
            }
        }
        LL b = -min(0LL, tr[1].minv);
        b = (b + k - 1) / k; // 多减了b次

        ans += d - b;
    }

    cout << ans << endl;
    return 0;
}