60ptsWA+TLE求助

之前发帖那个代码假了 那个就不是个分块 重写了

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
#define int long long
inline int read()
{
    char ch=getchar(); 
    int x=0,f=1; 
    while(ch<'0'||ch >'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,q,l,r,x;
char op[3];
const int Maxn=1e6+5,Maxk=1e3+5;
int a[Maxn],k[Maxn],s[Maxn];
int lt[Maxk],rt[Maxk];
int add[Maxk];
int block,tot;
inline void kp(int p)//sort in block p
{
    sort(s+lt[p],s+rt[p]+1);
}
void init()
{
    cin>>n>>q;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        s[i]=a[i]=read();
        k[i]=(i-1)/block+1;
    }
    tot=bool(n%block)+block;
    for(int i=1;i<=tot;i++)
    {
        lt[i]=(i-1)*block+1;
        rt[i]=i*block;
    }
    rt[k[n]]=n;
    for(int i=1;i<=tot;i++) kp(i);
}
void modify()
{
    if(k[r]-k[l]<=1)
    {
        for(int i=l;i<=r;i++) a[i]+=x;
        for(int i=lt[k[l]];i<=rt[k[r]];i++) s[i]=a[i];
        if(k[r]!=k[l]) kp(k[r]);
        kp(k[l]);
        return;
    }
    for(int i=l;i<=rt[k[l]];i++) a[i]+=x;
    for(int i=lt[k[r]];i<=r;i++) a[i]+=x;
    for(int i=lt[k[l]];i<=rt[k[l]];i++) s[i]=a[i];
    for(int i=lt[k[r]];i<=rt[k[r]];i++) s[i]=a[i];
    for(int i=k[l]+1;i<k[r];i++) add[i]+=x;
    kp(k[l]);
    kp(k[r]);
}
inline int search(int p)//search in block p
{
    int L=lt[p],R=rt[p],ans=rt[p]+1,mid;
    int goal=x-add[p];
    while(L<=R)
    {
        mid=(L+R)>>1;
        if(s[mid]>=goal)
        {
            ans=mid;
            R=mid-1;
        }
        else L=mid+1;
    }

    return rt[p]-ans+1;
}
inline int query()
{
    int ans=0;
    if(k[r]-k[l]<=1)
    {
        for(int i=l;i<=r;i++)
            if(a[i]+add[k[i]]>=x) ans++;
        return ans;
    }
    for(int i=l;i<=rt[k[l]];i++)
    {
        if(a[i]+add[k[i]]>=x) ans++;
    }
    for(int i=lt[k[r]];i<=r;i++)
    {
        if(a[i]+add[k[i]]>=x) ans++;
    }
    for(int i=k[l]+1;i<k[r];i++) ans+=search(i);
    return ans;
}
signed main()
{
    init();
    while(q--)
    {
        scanf("%s",&op);
        l=read();r=read();x=read();
        if(op[0]=='M') modify();
        else printf("%lld\n",query());
    }
}