!未封装.

每次操作 \(O(\sqrt{N} \log{N})\).

const int M = 8e2;
const int N = 1e6 + 10 + M;

array<int, N> arr, sorted;
array<int, N> add;

void build(int n) {
    n = (n + M - 1) / M * M + M;
    for (int i = 0; i < n; i++) {
        sorted[i] = arr[i];
        if (i % M == M - 1) {
            sort(sorted.begin() + (i - M + 1), sorted.begin() + i + 1);
        }
    }
}

void modify(int l, int r, int w) {
    if (l / M != r / M) {
        for (int i = l / M * M; i < l / M * M + M; i++) {
            arr[i] += add[l / M];
            if (i <= r && i >= l)
                arr[i] += w;
            sorted[i] = arr[i];
        }
        add[l / M] = 0;
        sort(sorted.begin() + l / M * M, sorted.begin() + l / M * M + M);
        for (int i = r / M * M; i < r / M * M + M; i++) {
            arr[i] += add[r / M];
            if (i <= r && i >= l)
                arr[i] += w;
            sorted[i] = arr[i];
        }
        add[r / M] = 0;
        sort(sorted.begin() + r / M * M, sorted.begin() + r / M * M + M);
        for (int i = l / M * M + M; i < r / M * M; i += M) {
            add[i / M] += w;
        }
    } else {
        for (int i = l / M * M; i < l / M * M + M; i++) {
            arr[i] += add[i / M];
            if (i <= r && i >= l)
                arr[i] += w;
            sorted[i] = arr[i];
        }
        add[l / M] = 0;
        sort(sorted.begin() + l / M * M, sorted.begin() + l / M * M + M);
    }
}

int query(int l, int r, int c) {
    int res = 0;
    for (int i = l; i <= r; i++) {
        if (i % M == 0 && i + M - 1 <= r) {
            res += sorted.begin() + i + M - lower_bound(sorted.begin() + i, sorted.begin() + i + M, c - add[i / M]);
            i += M - 1;
        } else {
            res += add[i / M] + arr[i] >= c;
        }
    }
    return res;
}

use: P2801 教主的魔法

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    build(n);
    while (q--) {
        char op;
        int l, r, w;
        cin >> op >> l >> r >> w;
        if (op == 'A') {
            cout << query(l - 1, r - 1, w) << '\n';
        } else {
            modify(l - 1, r - 1, w);
        }
    }
}