https://loj.ac/p/6278

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

const int N = 5e5 + 5;
int st[N], ed[N], a[N], pos[N], sum[N], add[N], b[N];

void update(int x, int y, int c)
{
    int p = pos[x], q = pos[y];
    if(p == q)
    {
        for(int i = x;i <= y;i ++ ) a[i] += c;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + ed[p] + 1);
    }
    else 
    {
        for(int i = p + 1;i < q;i ++ ) add[i] += c;
        for(int i = x;i <= ed[p];i ++ ) a[i] += c;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + ed[p] + 1);
        for(int i = st[q];i <= y;i ++ ) a[i] += c;
        for(int i = st[q];i <= ed[q];i ++ ) b[i] = a[i];
        sort(b + st[q], b + ed[q] + 1);
    }
}

int mid_find(int val, int x)
{
    int l = st[x], r = ed[x];
    int ans = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(a[mid] < val) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ans;
}

int query(int x, int y, int val)
{
    int p = pos[x], q = pos[y];
    int ans = 0;
    if(p == q)
    {
        for(int i = x;i <= y;i ++ ) {
            if(a[i] + add[p] < val) ans ++ ;
        }
    }
    else {
        for(int i = p + 1;i < q;i ++ ) ans += mid_find(val - add[i], i);
        for(int i = x;i <= ed[p];i ++ ){
            if(a[i] + add[p] < val) ans ++ ;
        }
        for(int i = st[q];i <= y;i ++ ) {
            if(a[i] + add[q] < val) ans ++ ;
        }
    }
    return ans;
}

signed main(){
    int n; cin >> n;

    for(int i = 1;i <= n;i ++ ) cin >> a[i],b[i] = a[i];
    int block = sqrt(n);
    int cnt = n / block;
    if(n % block) cnt ++ ;
    for(int i = 1;i <= cnt;i ++ ) st[i] = (i - 1) * block + 1, ed[i] = i * block;
    ed[cnt] = n;
    for(int i = 1;i <= cnt;i ++ ){
        for(int j = st[i];j <= ed[i];j ++ ) pos[j] = i;
    }
    for(int i = 1;i <= cnt;i ++ ) sort(b + st[i],b + ed[i] + 1);
    while(n -- )
    {
        int k, l, r, c;
        cin >> k >> l >> r >> c;
        if(k == 0){
            update(l, r, c);
        }
        else {
            cout << query(l, r, c * c) << endl;
        }
    }
    return 0;
}