分块WA50pts求调

WA #6——10

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,M=1e3+5;
int n,q,t,k;
int a[N],b[N],d[M],s[M],f[M],p[M];
void build(){
    for(int i=1;i<=n;i++){
        b[i]=(i-1)/k+1;
        d[i]=a[i];
    }
    for(int i=1;i<=t;i++){
        s[i]=(i-1)*k+1;
        f[i]=i*k; if(i==t) f[i]=n;
        sort(d+s[i],d+f[i]+1);
    }
}
void changeblock(int l,int r,int x){
    for(int i=s[b[l]];i<=f[b[l]];i++){
        if(l<=i&&i<=r) a[i]+=x;
        d[i]=a[i];
    }
    sort(d+s[b[l]],d+f[b[l]]+1);
}
void change(int l,int r,int x){
    if(b[l]==b[r]) changeblock(l,r,x);
    else{
        changeblock(l,f[b[l]],x);
        changeblock(s[b[r]],r,x);
        for(int i=b[l]+1;i<b[r];i++) p[i]+=x;
    }
}
int askblock(int l,int r,int x){
    int ans=0;
    for(int i=l;i<=r;i++) if(a[i]+p[b[i]]>=x) ans++;
    return ans;
}
int ask(int l,int r,int x){
    int ans=0;
    if(b[l]==b[r]) return askblock(l,r,x);
    ans+=askblock(l,f[b[l]],x)+askblock(s[b[r]],r,x);
    for(int i=b[l]+1;i<b[r];i++) ans+=f[i]+1-(lower_bound(d+s[i],d+f[i]+1,x-p[i])-d);
    return ans;
}
signed main(){
    cin>>n>>q;
    k=sqrt(n);
    t=n/k; if(n%k) t++;
    for(int i=1;i<=n;i++) cin>>a[i];
    build();
    for(int i=1;i<=q;i++){
        char op; int l,r,c;
        cin>>op>>l>>r>>c;
        if(op=='M') change(l,r,c);
        else cout<<ask(l,r,c)<<endl;
    }
    return 0;
}