30pts 分块板子求调

rt,过了 #3 #4 #10

#include<bits/stdc++.h>
using namespace std;
int n,q;
#define maxn 1000020
int a[maxn],b[maxn];
int h[maxn],lazy[maxn];
int L[maxn],R[maxn];
int block,num;
void init(){
    block=sqrt(n*__lg(n))+1;
    num=n/block;
    if(n%block)num++;
    for(int i=1;i<=n;i++)
        b[i]=(i-1)/block+1;
    for(int i=1;i<=num;i++)
        L[i]=(i-1)*block+1,R[i]=i*block;
    R[num]=n;
    for(int i=1;i<=n;i++)
        h[i]=a[i];
    for(int i=1;i<=num;i++)
        sort(h+L[i],h+R[i]+1);
}
int t[maxn];
void merge(int l1,int r1,int l2,int r2){
    int l=l1,r=r2;
    int cnt=l1;
    while(l1<=r1&&l2<=r2){
        if(h[l1]<h[r2])
            t[cnt++]=h[l1++];
        else
            t[cnt++]=h[l2]++;
    }
    while(l1<=r1)t[cnt++]=h[l1++];
    while(l2<=r2)t[cnt++]=h[l2++];
    for(int i=l;i<=r;i++)h[i]=t[i];
}
void add(int l,int r,int w){
    if(b[l]==b[r]){
        for(int i=l;i<=r;i++)a[i]+=w;
        for(int i=L[b[l]];i<=R[b[l]];i++)h[i]=a[i];
        sort(h+L[b[l]],h+R[b[l]]+1);
        return;
    }
    for(int i=b[l]+1;i<=b[r]-1;i++)lazy[i]+=w;
    for(int i=l;i<=R[b[l]];i++)a[i]+=w;
    for(int i=L[b[l]];i<=R[b[l]];i++)h[i]=a[i];
    sort(h+L[b[l]],h+R[b[l]]+1);
  //  merge(L[b[l]],l-1,l,R[b[l]]);
    for(int i=L[b[r]];i<=r;i++)a[i]+=w;
    for(int i=L[b[r]];i<=R[b[r]];i++)h[i]=a[i];
     sort(h+L[b[r]],h+R[b[r]]+1);
  //  merge(L[b[r]],r,r+1,R[b[r]]);
}
int query(int l,int r,int c){
    if(b[l]==b[r]){
        int ans=0;
        for(int i=l;i<=r;i++){
            if(h[i]+lazy[b[i]]>=c)ans++;
        }
        return ans;
    }
    int ans=0;
    for(int i=l;i<=R[b[l]];i++)if(h[i]+lazy[b[i]]>=c)ans++;
    for(int i=L[b[r]];i<=r;i++)if(h[i]+lazy[b[i]]>=c)ans++;
    for(int i=b[l]+1;i<=b[r]-1;i++){
        ans+=lower_bound(h+L[b[i]],h+R[b[i]]+1,c-lazy[i])-h;
    }
    return ans;
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    while(q--){
        char c;
        int l,r,w;
        cin>>c>>l>>r>>w;
        if(c=='M'){
            add(l,r,w);
      //      for(int i=1;i<=n;i++)cout<<h[i]<<" ";
      //      cout<<endl;
        }
        else{
            cout<<query(l,r,w)<<endl;
        }
    }
    return 0;
}