萌新求助分块

#2#9#10 WA  #4#5#6#7#8 T

QAQ，蒟蒻代码如下 码风见谅（具体思路与第二篇题解差不多）

#include<bits/stdc++.h>
using namespace std;

int t,n,q,pos[1000000+10],b[1000000+10],L[1000+10],R[1000+10],a[1000000+10],add[1000+10];

inline void make()
{
    t=sqrt(n);
    for(int i=1;i<=t;i++)
    {
        L[i]=(i-1)*sqrt(n)+1;
        R[i]=i*sqrt(n);
    }

    if(R[t]<n)
    {
        t++;    
        L[t]=R[t-1]+1;
        R[t]=n; 
    }

    for(int i=1;i<=t;i++)
      for(int j=L[i];j<=R[i];j++)
      {
         pos[j]=i;
      }

    for(int i=1;i<=t;i++){
        sort(b+L[i],b+R[i]+1);
    }
}

inline void change(int l,int r,int d)
{
    int posl=pos[l],posr=pos[r];

    if(posl==posr)
    {
        for(int i=l;i<=r;i++)
          a[i]+=d;
        for(int i=L[posl];i<=R[posr];i++)
          b[i]=a[i];
        sort(b+L[posl],b+R[posr]+1);
    }

    else
    {
        for(int i=posl+1;i<=posr-1;i++)
           add[i]+=d;

        for(int i=l;i<=R[posl];i++)
           a[i]+=d;
        for(int i=L[posl];i<=R[posl];i++)
           b[i]=a[i];
        sort(b+L[posl],b+R[posl]+1);

        for(int i=L[posr];i<=r;i++)
          a[i]+=d;
        for(int i=L[posr];i<=R[posr];i++)
          b[i]=a[i];  
        sort(b+L[posr],b+R[posr]+1);    
    }
}

int ask(int l,int r,int w)
{
    int posl=pos[l],posr=pos[r];
    int ans=0;

    if(posl==posr)
    {
        for(int i=l;i<=r;i++)
           if(add[posl]+a[i]>=w)
             ans++;
    }

    else
    {
        for(int i=posl+1;i<=posr-1;i++)
           {
              int ll=L[i],rr=R[i],mid,QAQ=0;
              while(ll<=rr)
              {
                  mid=(ll+rr)/2;
                  if(b[mid]+add[i]>=w)
                      {
                         rr=mid-1;
                         QAQ=R[i]-mid+1;
                      }
                  else
                      ll=mid+1;
              }
              ans+=QAQ;
           }

        for(int i=l;i<=R[posl];i++)
           if(add[posl]+a[i]>=w)
             ans++;

        for(int i=L[posr];i<=r;i++)
            if(add[posr]+a[i]>=w)
             ans++;
    }

    return ans;
} 

int main()
{
//  freopen("2.in","r",stdin);
//  freopen("1213.out","w",stdout);
    char ch[1];
    int l,r,w;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }   

    make();

    for(int i=1;i<=q;i++)
    {
        scanf("%s%d%d%d",ch,&l,&r,&w);

        if(ch[0]=='A')
        {
            printf("%d\n",ask(l,r,w));
        }

        else 
        {
            change(l,r,w);
        }
    }
}