分块90pts求调

rt:

#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define int long long
//#define double long double
#define FOR(i,l,r) for(int i=l;i<=r;++i)
#define ROF(i,r,l) for(int i=r;i>=l;--i)
#define mkp make_pair
#define fr first
#define se second
#define pb push_back
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
using namespace std;
const int N=1e6+10;
int n,q,a[N],len,tot,lft[N],id[N],rgt[N],b[N],tag[N];
void adde(int l,int r,int c) {
    int lc=id[l],rc=id[r];
    if(lc==rc) {
        FOR(i,l,r) b[i]+=c;
        sort(b+lft[lc],b+rgt[rc]+1);
        return ;
    }
    for(int i=l;id[i]==lc;++i) b[i]+=c;sort(b+lft[lc],b+rgt[lc]+1);
    FOR(i,lc+1,rc-1) tag[i]+=c;
    for(int i=r;id[i]==rc;--i) b[i]+=c;sort(b+lft[rc],b+rgt[rc]+1);
    return ; 
}
int ask(int l,int r,int c) {
    int lc=id[l],rc=id[r],res=0;
    if(lc==rc) {
        res+=(r-l+1)-(lower_bound(b+l,b+r+1,c-tag[lc])-b-l);
        return res;
    }
    for(int i=l;id[i]==lc;++i) if(b[i]>=c-tag[lc]) res++;
    FOR(i,lc+1,rc-1) res+=(rgt[i]-lft[i]+1)-(lower_bound(b+lft[i],b+rgt[i]+1,c-tag[i])-b-lft[i]);
    for(int i=r;id[i]==rc;--i) if(b[i]>=c-tag[rc]) res++;
    return res;
}
main() {
    cin>>n>>q;
    len=sqrt(n);
    tot=n/len+(bool)(n%len);
    FOR(i,1,n) {
        scanf("%lld",&a[i]);b[i]=a[i];
        id[i]=(i-1)/len+1;
        if(id[i]!=id[i-1]) lft[id[i]]=i,rgt[id[i-1]]=i-1;
    }
    rgt[id[n]]=n;
    FOR(i,1,tot) sort(b+lft[i],b+rgt[i]+1);
    while(q--) {
        char ch[2];
        int l,r,c;
        scanf("%s%lld%lld%lld",ch,&l,&r,&c);
        if(ch[0]=='M') adde(l,r,c);
        if(ch[0]=='A') printf("%lld\n",ask(l,r,c)); 
    }
    return 0;
}