抽象码风与做法求条

#include <bits/stdc++.h>
#define ri register int
using namespace std;

inline int read(){
    int ret=0; bool f=1; char c;
    while((c=getchar())<'0' || c>'9') if(c=='-') f=0;
    while(isdigit(c)) ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return f ? ret : ~ret+1;
}

int n,q,h[1000010],B,to[1000010],lazy[10010],a[1000010],W,c,ans,l,r;

void add(int sub){
    ri i=sub;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) h[j]+=lazy[to[sub]];
    while(to[i]==to[sub] && i<=r) h[i]+=W,i++;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) a[j]=h[j];
    sort(a+(to[sub]-1)*B+1,a+to[sub]*B);
    lazy[to[sub]]=0;
}

void addr(int sub){
    ri i=sub;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) h[j]+=lazy[to[sub]];
    while(to[i]==to[sub] && i>=l) h[i]+=W,i--;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) a[j]=h[j];
    sort(a+(to[sub]-1)*B+1,a+to[sub]*B);
    lazy[to[sub]]=0;
}

void find(int sub){
    ri i=sub;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) h[j]+=lazy[to[sub]];
    while(to[i]==to[sub] && i<=r) ans+=h[i]>=c,i++;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) a[j]=h[j];
    sort(a+(to[sub]-1)*B+1,a+to[sub]*B);
    lazy[to[sub]]=0;
}

void findr(int sub){
    ri i=sub;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) h[j]+=lazy[to[sub]];
    while(to[i]==to[sub] && i>=l) ans+=h[i]>=c,i--;
    for(ri j=(to[sub]-1)*B+1;j<=to[sub]*B;j++) a[j]=h[j];
    sort(a+(to[sub]-1)*B+1,a+to[sub]*B);
    lazy[to[sub]]=0;
}

int main(){
//  freopen("11.in","r",stdin);
//  freopen(".out","w",stdout);

    n=read(),q=read();
    B=(int)sqrt(n);
    for(ri i=1;i<=n;i++) to[i]=(i-1)/B+1;
    for(ri i=1;i<=n;i++) a[i]=h[i]=read();
    for(ri i=1;i<=n/B;i++) sort(a+(i-1)*B+1,a+i*B);
    while(q--){
        char ch=getchar();
        l=read(),r=read();
        if(ch=='M'){
            W=read();
            for(ri i=to[l]+1;i<to[r];i++) lazy[i]+=W;
            add(l);
            if(to[l]!=to[r]) addr(r);
        }
        else{
            c=read(),ans=0;
            for(ri i=to[l]+1;i<to[r];i++) ans+=a+i*B-lower_bound(a+(i-1)*B+1,a+i*B,c-lazy[i])+1,printf("%d %d %d %d\n",(i-1)*B+1,i*B,i,ans);
            find(l);
            if(to[l]!=to[r]) findr(r);
            printf("%lld\n",ans);
        }
    }

    return 0;
}//By ZCY  awa