求条 70 pts

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=500010;
int n,m,t,tot,l[N],r[N],a[N],b[N],laz[N],bel[N];
void build(){
    t=(int)(sqrt(n)),tot=(n-1)/t+1;
    for(int i=1;i<=tot;i++){
        l[i]=(i-1)*t+1,r[i]=i*t;
        sort(b+l[i],b+r[i]+1);
    }
    for(int i=1;i<=n;i++) bel[i]=(i-1)/t+1;
}
void add_(int x,int y,int z){
    for(int i=x;i<=y;i++) a[i]+=z;
    for(int i=l[bel[x]];i<=r[bel[x]];i++) b[i]=a[i];
    sort(b+l[bel[x]],b+r[bel[x]]+1);
}
void add(int x,int y,int z){
    if(bel[x]==bel[y]){
        add_(x,y,z);
        return;
    }
    add_(x,r[bel[x]],z);
    add_(l[bel[y]],y,z);
    for(int i=bel[x]+1;i<bel[y];i++) laz[i]+=z;
}
int query_(int x,int y,int z){
    int ans=0;
    for(int i=x;i<=y;i++){
        if(a[i]+laz[bel[x]]>=z) ans++;
    }
    return ans;
}
int query(int x,int y,int z){
    int ans=0;
    if(bel[x]==bel[y]) return query_(x,y,z);
    for(int i=bel[x]+1;i<bel[y];i++) ans+=r[i]-(lower_bound(b+l[i],b+r[i]+1,z-laz[i])-b)+1;
    return ans+query_(x,r[bel[x]],z)+query_(l[bel[y]],y,z);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    build();
    while(m--){
        char op;
        int x,y,z;
        cin>>op>>x>>y>>z;
        if(op=='M') add(x,y,z);
        else cout<<query(x,y,z)<<endl;
    }
    return 0;
}