好理解线段树题解 | #区间增量与区间小于计数#

线段树解决区间加上一个数, 用最大值最小值判断是否产生贡献

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 1e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream &operator>>(istream &is, i128 &val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char &c: str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream &operator<<(ostream &os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

struct Hash {
    vector<int> h, p;
    int B = 131;
    Hash (const string &s) {
        int n = s.size();
        h.resize(n + 1, 0);
        p.resize(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            p[i + 1] = p[i] * B % MOD;
            h[i + 1] = (h[i] * B + s[i]) % MOD;
        }
    }

    LL get(int l, int r) {
        LL v = h[r] - h[l - 1] * p[r - l + 1] % MOD;
        v = (v % MOD + MOD) % MOD;
        return v;
    }
};

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    struct T {
        struct Node {
            int l, r;
            LL mx;
            LL mn;
            LL add;
        };

        int n;
        vector<Node> tr;
        void init(int _n) {
            n = _n;
            tr.resize(4 * n + 10);
        }

        void pushup(int u) {
            Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];
            tr[u].mx = max(ls.mx, rs.mx);
            tr[u].mn = min(ls.mn, rs.mn);
        }

        void pushdown(int u) {
            if (tr[u].add) {
                Node &ls = tr[u << 1], &rs = tr[u << 1 | 1];
                ls.add += tr[u].add, rs.add += tr[u].add;
                ls.mx += tr[u].add, rs.mx += tr[u].add;
                ls.mn += tr[u].add, rs.mn += tr[u].add;
                tr[u].add = 0;
            }
        }

        void build(int u, int l, int r, vector<int> &a) {
            tr[u] = {l, r, -INF, INF, 0};
            if (l == r) {
                tr[u].mx = tr[u].mn = a[l];
                return;
            }
            int mid = l + r >> 1;
            build(u << 1, l, mid, a);
            build(u << 1 | 1, mid + 1, r, a);
            pushup(u);
        }

        void add(int u, int ql, int qr, LL v) {
            if (tr[u].l >= ql && tr[u].r <= qr) {
                tr[u].add += v;
                tr[u].mx += v;
                tr[u].mn += v;
                return;
            }

            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (ql <= mid) add(u << 1, ql, qr, v);
            if (qr > mid) add(u << 1 | 1, ql, qr, v);
            pushup(u);
        }

        LL query(int u, int ql, int qr, LL x) {
            if (tr[u].l >= ql && tr[u].r <= qr) {
                if (tr[u].mx < x) {
                    return tr[u].r - tr[u].l + 1;
                }
                if (tr[u].mn >= x) return 0;
            }

            if (tr[u].l == tr[u].r) {
                if (tr[u].l >= ql && tr[u].r <= qr && tr[u].mn < x) return 1;
                return 0;
            }

            LL ans = 0;
            pushdown(u);
            int mid = tr[u].l + tr[u].r >> 1;
            if (ql <= mid) ans += query(u << 1, ql, qr, x);
            if (qr > mid) ans += query(u << 1 | 1, ql, qr, x);
            return ans;
        }
    } t;

    t.init(n);
    t.build(1, 1, n, a);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            LL l, r, x;
            cin >> l >> r >> x;
            t.add(1, l, r, x);
        }
        else {
            LL l, r, x;
            cin >> l >> r >> x;
            cout << t.query(1, l, r, x) << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}