分块10pts求救

提交记录

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,T,a[1000005],s[1000005],block[1000005];
int block_l[1005],block_r[1005],add[1005];
void change(int l,int r,int d)
{
    int x_l=block[l],x_r=block[r];
    if(x_l==x_r)
    {
        for(int i=l;i<=r;i++)
        {
            a[i]+=d;
            s[i]=a[i];
        }
        sort(s+block_l[x_l],s+block_r[x_l]+1);
        return;
    }
    if(block_l[x_l]!=l)
    {
        for(int i=l;i<=block_r[x_l];i++)
        {
            a[i]+=d;
            s[i]=a[i];
        }
        sort(s+block_l[x_l],s+block_r[x_l]+1);
        x_l++;
    }
    if(block_r[x_r]!=r)
    {
        for(int i=block_l[x_r];i<=r;i++)
        {
            a[i]+=d;
            s[i]=a[i];
        }
        sort(s+block_l[x_r],s+block_r[x_r]+1);
        x_r--;
    }
    for(int i=x_l;i<=x_r;i++)
    {
        add[i]+=d;
    }
    return;
} 
int ask(int l,int r,int c)
{
    int x_l=block[l],x_r=block[r];
    if(x_l==x_r)
    {
        int cnt=0;
        for(int i=l;i<=r;i++)
        {
            cnt+=(a[i]+add[x_l])>=c;
        }
        return cnt;
    }
    int cnt=0;
    if(l!=block_l[x_l])
    {
        for(int i=l;i<=block_r[x_l];i++)
        {
            cnt+=(a[i]+add[x_l])>=c;
        }
        x_l++;
    }
    if(r!=block_r[x_r])
    {
        for(int i=block_l[x_r];i<=r;i++)
        {
            cnt+=(a[i]+add[x_r])>=c;
        }
        x_r--;
    }
    for(int i=x_l;i<=x_r;i++)
    {
        int ll=block_l[i]-1,rr=block_r[i]+1;
        while(ll+1!=rr)
        {
            int mid=(ll+rr)>>1;
            if(s[mid]+add[i]>=c)rr=mid;
            else ll=mid;
        }
        if(rr==block_r[i]+1)continue;
        cnt+=block_r[i]-rr;
    }
    return cnt;
}
int main()
{
    scanf("%d%d",&n,&T);
    int t=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=t;i++)
    {
        block_l[i]=t*(i-1)+1;
        block_r[i]=t*i;
        for(int j=block_l[i];j<=block_r[i];j++)
        {
            s[j]=a[j];
            block[j]=i;
        }
        sort(s+block_l[i],s+block_r[i]+1);
    }
    if(block_r[t]!=n)
    {
        block_l[t+1]=t*t+1;
        block_r[t+1]=n;
        for(int j=block_l[t+1];j<=block_r[t+1];j++)
        {
            s[j]=a[j];
            block[j]=t+1;
        }
        sort(s+block_l[t+1],s+block_r[t+1]+1);      
    }
    while(T--)
    {
        char c;
        cin>>c;
        if(c=='M')
        {
            int l,r,w;
            scanf("%d%d%d",&l,&r,&w);
            change(l,r,w);
        }
        else
        {
            int l,r,c;
            scanf("%d%d%d",&l,&r,&c);
            printf("%d\n",ask(l,r,c));
        }
    } 
    return 0;
}