【分块+二分】 教主的魔法

题意： 有一个长度为n的数组，有m次操作，操作M L R X 为将 [L,R] 区间内所有的值加上x，操作 A L R C为询问 [L,R] 区间有多少数是大于等于C的。 分析：

1. 对于添加操作，利用分块算法快速地将 L,R 区间内的值加上x，具体操作为暴力加L到L所在区块的右边界，然后将 (L,R) 范围内的所有值打上懒标记。
2. 对于查询操作，我们在维护区块的值的时候同时维护区块内的排序，所以对于每一个区块，他都是一个整齐的序列，那么查询的时候就可以查询二分 查找L,R 区间内，每一个区块的C的位置，并由此转化成数量即可。

变量含义

• a[i]: 数组第i个元素的值
• d[i]: 临时数组，用来存分块后，每一块排序后的元素
• belong[i]: 第i个数组所属于的区块
• lazy[i]: 懒标记，第i个区块都需要进行+的值
• L[i]: 第i个区块的左边界
• R[i]: 第i给区块的右边界

build()

分块函数，用于初始化区块。 每一块的大小为$√n$,那么一共有 $n/√n+(n$ 个区块

void build()
{
  block=sqrt(n);
  tot=n/block;
  if( n%block ) tot++;
  
区块大小和个数
  for(int i=1;i<=n;i++)
  {
    belong[i]=(i-1)/block+1;d[i]=a[i];
   //每一个元素是属于哪一块的，并把值赋给临时数组
  }
  for(int i=1;i<=tot;i++)
  {
    L[i]=(i-1)*block+1,R[i]=i*block;
    //区块左边界和右边界  
}
  R[tot]=n;  //右边界为n
  for(int i=1;i<=tot;i++)
  {
    sort(d+L[i],d+R[i]+1);
//对临时数组排序
  }
}

change()

对 [l,r] 区间的值进行更改的函数，主要为两个内容

1. 但l，r属于同一区块的时候，a数组的值暴力从l一直加到r，并维护这个区间的集合
2. 当l，r不属于同一个区块的时候，暴力从 l 加到 l 区块的末尾，然后维护 l 所在区块的顺序。然后在（l,r) 区间内的所有区块都只打上一个懒标记，不需要维护顺序，因为顺序不会变的。然后暴力维护 r 所在区块就可以了

void change()
{
  if(belong[x]==belong[y]) //暴力维护l，r所在区块
  {
    for(int i=x;i<=y;i++)
      a[i]+=k;
    for(int i=L[belong[x]];i<=R[belong[x]];i++ )
      d[i]=a[i];
    sort( d+L[belong[x]],d+R[belong[x]]+1 );
  }
  else{
//维护l区块
    for(int i=x;i<=R[belong[x]];i++)
    {
      a[i]+=k;
    }
    for(int i=L[belong[x]];i<=R[belong[x]];i++)
    {
      d[i]=a[i];
    }
    sort(d+L[belong[x]],d+R[belong[x]]+1);

  //维护r区块
    for(int i=L[belong[y]];i<=y;i++)
    {
      a[i]+=k;
    }
    for(int i=L[belong[y]];i<=R[belong[y]];i++)
    {
      d[i]=a[i];
    }
    sort(d+L[belong[y]],d+R[belong[y]]+1);
    
// (l,r) 区间内的区块打上懒标记
  for(int i=belong[x]+1;i<=belong[y]-1;i++)
    lazy[i]+=k;
  }
}

query()

用二分；

1. 如果 l与r 属于同一个区块的话，只需要二分查找 c-lazy 在 d[l,r] 的位置就可以了
2. 如果不在同一个区块，只需要求 l 所在区块，（ l , r ） 之间所有区块， r 所在区块的所有的结果并相加就可以了。

void query()
{
  ans=0;
  if(belong[x]==belong[y])
  {
    for(int i=x;i<=y;i++)
      if( lazy[belong[x]]+a[i]>=k ) ans++;
    cout<<ans<<endl;
    return;
  }
  for(int i=x;i<=R[belong[x]];i++)
  {
    if( lazy[belong[x]]+a[i]>=k ) ans++;
  }
  for(int i=L[belong[y]];i<=y;i++)
  {
    if( lazy[belong[y]]+a[i]>=k ) ans++;
  }
  for(int i=belong[x]+1;i<=belong[y]-1;i++)
  {
    int ll=L[i],rr=R[i],result=0,mid;
    while(ll<=rr)
    {
      mid=(ll+rr)>>1;
      if( d[mid]+lazy[i]>=k )
          rr=mid-1,result=R[i]-mid+1;
      else ll=mid+1;
    }
    ans+=result;
  }
  cout<<ans<<endl;
}

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+12;
int a[N],d[N],L[1007],R[1007],belong[N],lazy[1007],ans;
int n,q,block,tot,x,y,k;
char cz;
void build()
{
  block=sqrt(n);
  tot=n/block;
  if( n%block ) tot++;
  for(int i=1;i<=n;i++)
  {
    belong[i]=(i-1)/block+1;d[i]=a[i];
  }
  for(int i=1;i<=tot;i++)
  {
    L[i]=(i-1)*block+1,R[i]=i*block;
  }
  R[tot]=n;
  for(int i=1;i<=tot;i++)
  {
    sort(d+L[i],d+R[i]+1);
  }
}
void change()
{
  if(belong[x]==belong[y])
  {
    for(int i=x;i<=y;i++)
      a[i]+=k;
    for(int i=L[belong[x]];i<=R[belong[x]];i++ )
      d[i]=a[i];
    sort( d+L[belong[x]],d+R[belong[x]]+1 );
  }
  else{
    for(int i=x;i<=R[belong[x]];i++)
    {
      a[i]+=k;
    }
    for(int i=L[belong[x]];i<=R[belong[x]];i++)
    {
      d[i]=a[i];
    }
    sort(d+L[belong[x]],d+R[belong[x]]+1);
    for(int i=L[belong[y]];i<=y;i++)
    {
      a[i]+=k;
    }
    for(int i=L[belong[y]];i<=R[belong[y]];i++)
    {
      d[i]=a[i];
    }
    sort(d+L[belong[y]],d+R[belong[y]]+1);
    for(int i=belong[x]+1;i<=belong[y]-1;i++)
    lazy[i]+=k;
  }
}
void query()
{
  ans=0;
  if(belong[x]==belong[y])
  {
    for(int i=x;i<=y;i++)
      if( lazy[belong[x]]+a[i]>=k ) ans++;
    cout<<ans<<endl;
    return;
  }
  for(int i=x;i<=R[belong[x]];i++)
  {
    if( lazy[belong[x]]+a[i]>=k ) ans++;
  }
  for(int i=L[belong[y]];i<=y;i++)
  {
    if( lazy[belong[y]]+a[i]>=k ) ans++;
  }
  for(int i=belong[x]+1;i<=belong[y]-1;i++)
  {
    int ll=L[i],rr=R[i],result=0,mid;
    while(ll<=rr)
    {
      mid=(ll+rr)>>1;
      if( d[mid]+lazy[i]>=k )
          rr=mid-1,result=R[i]-mid+1;
      else ll=mid+1;
    }
    ans+=result;
  }
  cout<<ans<<endl;
}
int main(){
  cin>>n>>q;
  for(int i=1;i<=n;i++)
    cin>>a[i];
  build();
  while(q--)
  {
    cin>>cz>>x>>y>>k;
    if( cz=='M' )
      change();
    else query();

  }



}