题面

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 114514;
const int maxm = 434;
int n;
int a[maxn];
int a_[maxn];
int b[maxn];//区间加上的数
int query_k(int id) {
    int ret = id / maxm;

    if (id % maxm)
        ret++;

    return ret;
}
int binary(int l, int r, int num) {
    //  cout<<l<<' '<<r<<endl;
    int mid = l + r >> 1;

    while (l < r) {
        //      cout<<l<<' '<<r<<endl;
        if (a_[mid] > num)
            r = mid;
        else
            l = mid + 1;

        mid = l + r >> 1;
    }

    if (a_[mid] >= num)
        return mid - l;
    else
        return mid - l + 1;
}
signed main() {
    //  freopen("t2.in","r",stdin);
    scanf("%lld", &n);

    //  while(n--){
    //      int x;
    //      cin>>x;
    //      cout<<query_k(x)<<endl;
    //  }
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        a_[i] = a[i];
    }

    for (int i = 1;; i++) {
        int j1 = (i - 1) * maxm + 1;
        int j2 = min(i * maxm, n);
        sort(a_ + j1, a_ + j2 + 1);

        if (j2 >= n)
            break;
    }

    int q = n;

    while (q--) {
        int op;
        int l, r;
        int c;
        scanf("%lld", &op);

        if (op == 0) {
            scanf("%lld%lld", &l, &r);
            scanf("%lld", &c);
            int l1 = query_k(l);
            int r1 = query_k(r);
            int j1, j2;

            if (l1 == r1) {
                for (int i = l; i <= r; i++) {
                    a[i] += c;
                }

                j1 = (l1 - 1) * maxm + 1;
                j2 = min(n, l1 * maxm);

                for (int i = j1; i <= j2; i++) {
                    a_[i] = a[i];
                }

                sort(a_ + j1, a_ + j2 + 1);
            } else {
                j2 = min(l1 * maxm, n);

                for (int i = l; i <= j2; i++) {
                    a[i] += c;
                }

                j1 = (l1 - 1) * maxm + 1;

                for (int i = j1; i <= j2; i++) {
                    a_[i] = a[i];
                }

                sort(a_ + j1, a_ + j2 + 1);
                j1 = (r1 - 1) * maxm + 1;
                j2 = min(n, r1 * maxm);

                for (int i = j1; i <= r; i++) {
                    a[i] += c;
                }

                for (int i = j1; i <= j2; i++) {
                    a_[i] = a[i];
                }

                sort(a_ + j1, a_ + j2 + 1);

                for (int i = l1 + 1; i < r1; i++) {
                    b[i] += c;
                }
            }
        } else {
            int ans = 0;
            scanf("%lld%lld", &l, &r);
            scanf("%lld", &c);
            c *= c;
            int l1 = query_k(l);
            int r1 = query_k(r);

            if (l1 == r1) {
                for (int i = l; i <= r; i++) {
                    ans += (a[i] + b[query_k(i)] < c);
                }

                printf("%lld\n", ans);
            } else {
                int j1, j2;
                j2 = l1 * maxm;

                for (int i = l; i <= j2; i++) {
                    ans += (a[i] + b[l1] < c);
                }

                j1 = (r1 - 1) * maxm + 1;

                for (int i = j1; i <= r; i++) {
                    ans += (a[i] + b[r1] < c);
                }

                for (int i_ = l1 + 1; i_ < r1; i_++) {
                    int j1 = (i_ - 1) * maxm + 1;
                    int j2 = i_ * maxm;

                    if (a_[j1] + b[i_] >= c) {
                        ans += 0;
                    } else if (a_[j2] + b[i_] < c) {
                        ans += (j2 - j1 + 1);
                    } else {
                        ans += binary(j1, j2, c - b[i_]);
                    }
                }

                printf("%lld\n", ans);
            }
        }

        //      for(int i=1;i<=n;i++){
        //          cout<<a_[i]<<endl;
        //      }
        //      cout<<endl;
    }

    printf("\n");
    return 0;
}

@s_o_t_b

@Mugino_Shizuri