块状数组板子 ps记得初始化t数组。

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

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int N = 1e6+10;

ll a[N],delta[N],st[N],ed[N],belong[N],t[N];
//a原始数组 delta标记 st块起点 ed块终点 belong属于块编号
//t排序后数组用于计算一个块内的答案 
int n,q;

void Sort(int k){
    for(int i=st[k];i<=ed[k];i++) t[i] = a[i];
    sort(t+st[k],t+ed[k]+1);
}
void modify(int l,int r,int c){
    int x=belong[l],y = belong[r];
    if(x==y){
        for(int i=l;i<=r;i++) a[i]+=c;
        Sort(x);
        return;
    }
    for(int i=l;i<=ed[x];i++) a[i]+=c;
    for(int i=x+1;i<y;i++) delta[i]+=c;
    for(int i=st[y];i<=r;i++) a[i]+=c;
    Sort(x);
    Sort(y);
}
ll query(int l,int r,int c){
    ll ans = 0;
    int x=belong[l],y = belong[r];
    if(x==y){
        for(int i=l;i<=r;i++) 
            if(a[i]+delta[x]>=c) ans++;
        return ans;
    }
    for(int i=l;i<=ed[x];i++)
        if(a[i]+delta[x]>=c) ans++;
    for(int i=st[y];i<=r;i++) 
        if(a[i]+delta[y]>=c) ans++;

    for(int i=x+1;i<y;i++){
            ans +=ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, c - delta[i]) - t) + 1;
        //cout<<ed[i]<<" "<<lower_bound(t + st[i], t + ed[i] + 1, c - delta[i]) - t<<endl;
    }
    return ans;
}

int main(){     
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];

    int num = sqrt(n);
    for(int i=1;i<=num;i++){
        st[i] = n/num*(i-1)+1; ed[i] = n/num * i;
        Sort(i);
    }
    ed[num] = n;
    for(int i=1;i<=num;i++)
        for(int j=st[i];j<=ed[i];j++){
            belong[j] = i;
        }

    while(q--){
        char op;
        int l,r,w;
        cin>>op>>l>>r>>w;
        if(op=='M'){
            modify(l,r,w);
        }else{
            cout<<query(l,r,w)<<endl;
        }
    }


    return 0;
}