记录编号	588144	评测结果	AAAAAAAAAA
题目名称	新年快乐！	最终得分	100
用户昵称	zxhhh	是否通过	通过
代码语言	C++	运行时间	9.089 s
提交时间	2024-05-27 18:27:53	内存使用	7.27 MiB

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

using namespace std;
const int N = 1e5+5, b = 355, B = 557; 
int n, m, bl[B], br[B], rk[N], z[N]; 
ll a[N], ad[B]; 
bool cmp (int x, int y) {
    return a[x] < a[y]; 
}

void add (int l, int r, ll k) {
    int lb = rk[l], rb = rk[r]; 
    if (lb == rb) {
        for (int i = bl[lb];i <= br[lb];i++) if (l <= z[i] && z[i] <= r) a[z[i]] += k; 
        sort(z+bl[lb], z+br[lb]+1, cmp); 
        return; 
    }
    for (int i = bl[lb];i <= br[lb];i++) if (l <= z[i] && z[i] <= r) a[z[i]] += k; 
    sort(z+bl[lb], z+br[lb]+1, cmp); 
    for (int i = bl[rb];i <= br[rb];i++) if (l <= z[i] && z[i] <= r) a[z[i]] += k; 
    sort(z+bl[rb], z+br[rb]+1, cmp); 
    for (int i = lb+1;i < rb;i++) ad[i] += k; 
}

int query (int l, int r, ll k) {
    int lb = rk[l], rb = rk[r], cnt = 0; 
    if (lb == rb) {
        for (int i = bl[lb];i <= br[lb];i++) if (l <= z[i] && z[i] <= r && a[z[i]]+ad[lb] <= k) cnt++;  
        return cnt;  
    }
    for (int i = bl[lb];i <= br[lb];i++) if (l <= z[i] && z[i] <= r && a[z[i]]+ad[lb] <= k) cnt++;  
    for (int i = bl[rb];i <= br[rb];i++) if (l <= z[i] && z[i] <= r && a[z[i]]+ad[rb] <= k) cnt++;  
    for (int i = lb+1;i < rb;i++) {
        int tl = bl[i], tr = br[i]; 
        while (tl < tr) {
            int mid = tl+tr+1>>1; 
            if (a[z[mid]]+ad[i] <= k) tl = mid;
            else tr = mid-1; 
        }
        if (a[z[tl]]+ad[i] <= k) cnt += tl-bl[i]+1; 
    }
    return cnt; 
}

int main () {
    freopen("dss.in", "r", stdin); 
    freopen("dss.out", "w", stdout); 
    cin >> n;
    rk[n] = (n+b-1)/b; 
    for (int i = 1;i <= rk[n];i++) {
        bl[i] = i*b-b+1; br[i] = min(i*b, n); 
        for (int j = bl[i];j <= br[i];j++) rk[j] = i; 
    }
    for (int i = 1;i <= n;i++) cin >> a[i]; 
    for (int i = 1;i <= n;i++) z[i] = i; 
    for (int i = 1;i <= rk[n];i++) sort(z+bl[i], z+br[i]+1, cmp); 
    cin >> m; 
    while (m--) {
        int op, l, r; ll k; 
        cin >> op >> l >> r >> k; 
        if (op == 1) add(l, r, k); 
        else cout << query(l, r, k) << '\n'; 
    }
    return 0; 
}