给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。 对于 100% 的数据，1 $\leq$ n $\leq$ 50000, -2^{31} $\leq$ $\mathrm{others}$、$\mathrm{ans}$ $\leq$ 2^{31}-1。

50分，超时,求助，QwQ

#include <bits/stdc++.h>
using namespace std;
int blk, bel[50005], d[250], lazy[250], bgn[250], End[250], n;
struct WZC {
    int num, id;
    bool operator<(const WZC T) {
        return num < T.num;
    }
} a[50005];
void start() {
    blk = sqrt(n);

    for (int i = 1; i <= n; i++) {
        if (i % blk == 1)
            bel[i] = bel[i - 1] + 1, bgn[bel[i]] = i, End[bel[i] - 1] = i - 1;

        bel[i] = bel[i - 1];
        d[bel[i]] += a[i].num;
    }

    End[bel[n]] = n;

    for (int i = 1; i <= bel[n]; i++)
        sort(a + bgn[i], a + End[i] + 1);
}
void update(int l, int r, int c) {
    int bl = bel[l], br = bel[r];

    if (bl == br) {
        for (int i = bgn[bl]; i <= End[bl]; i++)
            if (a[i].id >= l && a[i].id <= r)
                a[i].num += c;

        sort(a + bgn[bl], a + End[bl] + 1);
        return;
    }

    for (int i = bgn[bl]; i <= End[bl]; i++)
        if (a[i].id >= l && a[i].id <= r)
            a[i].num += c;

    sort(a + bgn[bl], a + End[bl] + 1);

    for (int i = bgn[br]; i <= End[br]; i++)
        if (a[i].id >= l && a[i].id <= r)
            a[i].num += c;

    sort(a + bgn[br], a + End[br] + 1);

    for (int i = bgn[bl] + 1; i <= End[br] - 1; i++)
        lazy[i] += c;
}
int query(int l, int r, int k) {
    int bl = bel[l], br = bel[r], ans = 0;

    if (bl == br) {
        for (int i = bgn[bl]; i <= End[bl]; i++)
            if (a[i].id >= l && a[i].id <= r && a[i].num + lazy[bl] < k)
                ans++;

        return ans;
    }

    for (int i = bgn[bl]; i <= End[bl]; i++)
        if (a[i].id >= l && a[i].id <= r && a[i].num + lazy[bl] < k)
            ans++;

    for (int i = bgn[br]; i <= End[br]; i++)
        if (a[i].id >= l && a[i].id <= r && a[i].num + lazy[br] < k)
            ans++;

    for (int i = bgn[bl] + 1; i <= End[br] - 1; i++)
        ans += lower_bound(a + bgn[i], a + End[i] + 1, WZC{k - lazy[i], 0}) - a - bgn[i];
    return ans;
}
int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].num);
        a[i].id = i;
    }

    start();

    for (int i = 1; i <= n; i++) {
        int op, l, r, c;
        scanf("%d%d%d%d", &op, &l, &r, &c);

        if (op == 0)
            update(l, r, c);

        if (op == 1)
            cout << query(l, r, c * c) << endl;
    }
}