官方题解

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n, B;
int a[200000], b[200000], c[200000];
void resort(int id) {
    int l = id * B;
    int r = min(l + B - 1, n - 1);
    for (int i = l; i <= r; ++i) c[i] = a[i];
    sort(c + l, c + r + 1);
}
int query(int id, int val) {
    int l = id * B;
    int r = min(l + B - 1, n - 1);
    val -= b[id];
    if (c[l] >= val)
        return 0;
    int b = l, e = r;
    while (b + 1 < e) {
        int mid = (b + e) / 2;
        if (c[mid] < val)
            b = mid;
        else
            e = mid;
    }
    if (c[e] < val)
        return e - l + 1;
    else if (c[b] < val)
        return b - l + 1;
    else
        return 0;
}
signed main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &a[i]);
        c[i] = a[i];
    }
    B = sqrt(n / 3);
    for (int l = 0; l < n; l += B) {
        int r = min(l + B - 1, n - 1);
        sort(c + l, c + r + 1);
    }

    // 1 ~ n,  0 ~ n - 1
    for (int i = 1; i <= n; ++i) {
        int op, l, r, c;
        scanf("%lld", &op);
        scanf("%lld %lld %lld", &l, &r, &c);
        if (op == 0) {
            l--, r--;
            int _l = l, _r = r;
            for (; l % B != 0 && l <= r; l++) a[l] += c;
            for (; l + B - 1 <= r; l += B) b[l / B] += c;
            for (; l <= r; ++l) a[l] += c;
            resort(_l / B);
            if (_l / B != _r / B)
                resort(_r / B);
        } else {
            l--, r--;
            int ans = 0;
            for (; l % B != 0 && l <= r; l++)
                if (a[l] + b[l / B] < c * c)
                    ans++;
            for (; l + B - 1 <= r; l += B) ans += query(l / B, c * c);
            for (; l <= r; ++l)
                if (a[l] + b[l / B] < c * c)
                    ans++;
            printf("%lld\n", ans);
        }
    }
    return 0;
}