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