题解 | 区间增量与区间小于计数

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

using namespace std;

const int N = 1e5+5;

int n, q;
int a[N];
int tag[N<<2], maxn[N<<2], minn[N<<2];

inline int read(){
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = x*10 + c - '0';
        c = getchar();
    }
    return x*f;
}

inline void pushup(int p){
    maxn[p] = max(maxn[p<<1], maxn[p<<1|1]);
    minn[p] = min(minn[p<<1], minn[p<<1|1]);
}

inline void pushdown(int p){
    minn[p<<1] += tag[p];
    minn[p<<1|1] += tag[p];
    maxn[p<<1] += tag[p];
    maxn[p<<1|1] += tag[p];
    tag[p<<1] += tag[p];
    tag[p<<1|1] += tag[p];
    tag[p] = 0;
}

inline void build(int p = 1, int cl = 1, int cr = n){
    if(cl == cr){
        maxn[p] = a[cl];
        minn[p] = a[cl];
        tag[p] = 0;
        return;
    }
    int cmid = cl+cr>>1;
    build(p<<1, cl, cmid);
    build(p<<1|1, cmid+1, cr);
    pushup(p);
}

inline void update(int l, int r, int k, int p = 1, int cl = 1, int cr = n){
    if(cl >= l && cr <= r){
        //cout<<cl<<' '<<cr<<'\n';
        maxn[p] += k;
        minn[p] += k;
        tag[p] += k;
        return;
    }
    int cmid = cl+cr>>1;
    pushdown(p);
    if(l <= cmid) update(l, r, k, p<<1, cl, cmid);
    if(r > cmid) update(l, r, k, p<<1|1, cmid+1, cr);
    pushup(p);
}

inline int query(int l, int r, int x, int p = 1, int cl = 1, int cr = n){
    if(cl >= l && cr <= r && maxn[p] < x){
        //cout<<cl<<' '<<cr<<' '<<maxn[p]<< ' '<< tag[p] <<'\n';
        return cr - cl + 1;
    }
    if(cl >= l && cr <= r && minn[p] >= x){
        return 0;
    }
    if(cl == cr){
        if(maxn[p] < x) return 1;
        else return 0;
    }
    int cmid = cl+cr>>1;
    int res = 0;
    pushdown(p);
    if(l<=cmid && r>cmid) return query(l,r,x,p<<1,cl,cmid)+query(l,r,x,p<<1|1,cmid+1,cr);
    else if(r<=cmid) return query(l,r,x,p<<1,cl,cmid);
    else return query(l,r,x,p<<1|1,cmid+1,cr);
}

signed main(){
    n = read(), q = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build();
    while(q--){
        int op, l, r, x;
        op = read(), l = read(), r = read(), x = read();
        if(op == 1){
            update(l,r,x);
        }
        else{
            cout<<query(l,r,x)<<'\n';
        }
    }
    return 0;
}