MnZn求助分块10pts

#include<bits/stdc++.h>
#define rep(i,st,ed,val) for(int i=st;i<=ed;i+=val)
#define Rep(i,st,ed,val) for(int i=st;i>=ed;i-=val)
#define int long long
using namespace std;
static constexpr int N=1e6+10;
int n,m;
int a[N];
int blo,cnt;
int L[N],R[N],bel[N];
int lz[N],b[N];
int p[N],p1[N],p2[N];

inline bool cmp(int x,int y){
    return a[x]<a[y];
}

inline void build(){
    blo=sqrt(n+1);
    cnt=(n+blo-1)/blo;
    rep(i,1,cnt,1){
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    R[cnt]=n;
    rep(i,1,n,1){
        bel[i]=(i-1)/blo+1;
        lz[bel[i]]=0;
    }
    rep(i,1,cnt,1){
        sort(p+L[i],p+R[i]+1,cmp);
    }
    rep(i,1,n,1){
        b[i]=a[p[i]];
    }
    return ;
}

inline void makeit(int id,int l,int r){
    int cnt1=0,cnt2=0;
    rep(i,L[id],R[id],1){
        if(l<=p[i] && p[i]<=r){
            p1[++cnt1]=p[i];
        }
        else{
            p2[++cnt2]=p[i];
        }
    }
    merge(p1+1,p1+cnt1+1,p2+1,p2+cnt2+1,p+L[id],cmp);
    rep(i,L[id],R[id],1){
        b[i]=a[p[i]];
    }
}

inline void modify(int l,int r,int val){
    if(bel[l]==bel[r]){
        rep(i,l,r,1){
            a[i]+=val;
        }
        makeit(bel[l],L[bel[l]],R[bel[l]]);
        return ;
    }
    rep(i,l,R[bel[l]],1){
        a[i]+=val;
    }
    Rep(i,r,L[bel[r]],1){
        a[i]+=val;
    }
    makeit(bel[l],l,R[bel[l]]);
    makeit(bel[r],L[bel[r]],r);
    rep(i,bel[l]+1,bel[r]-1,1){
        lz[bel[i]]+=val;
    }
    return ;
}

inline int query(int l,int r,int k){
    int ans=0;
    if(bel[l]==bel[r]){
        rep(i,l,r,1){
            ans+=((a[i]+lz[bel[i]])>=k);
        }
        return ans;
    }
    rep(i,l,R[bel[l]],1){
        ans+=((a[i]+lz[bel[i]])>=k);
    }
    Rep(i,r,L[bel[r]],1){
        ans+=((a[i]+lz[bel[i]])>=k);
    }
    rep(i,bel[l]+1,bel[r]-1,1){
        //cerr<<k-lz[i]<<'\n';
        ans+=(b+R[i]-lower_bound(b+L[i],b+R[i]+1,k-lz[i])+1);
        //cout<<(upper_bound(b+L[i],b+R[i],k-lz[i])-(b+L[i]))<<"\n";
    }
    return ans;
}

inline void doit(){
/*  ios::sync_with_stdio(NULL);
    cin.tie(NULL),cout.tie(NULL);*/
    cin>>n>>m;
    rep(i,1,n,1){
        cin>>a[i];
        p[i]=i;
    }
    build();
    rep(i,1,m,1){
        char opt;
        int l,r,k;
        cin>>opt>>l>>r>>k;
        if(opt=='M'){
            modify(l,r,k);
        }
        else{
            cout<<query(l,r,k)<<'\n';
//          rep(i,1,n,1){
//              cout<<a[i]<<" ";
//          }
//          cout<<"\n";
//          rep(i,1,cnt,1){
//              cout<<lz[i]<<" ";
//          }
//          cout<<"\n";
//          rep(i,1,n,1){
//              cout<<b[i]<<" ";
//          }
//          cout<<"\n";
        }
    }
}
signed main(){
    doit();
    return 0;
}