##

分块是个好东西

一般的区间模拟（或其他）的题基本上都可以那分块来做。

相对于线段树。分块还有其他的功能，比如说这一道题的查询在一个区间内比一个变量大的数有几个。

这种问题如果用线段树写。那么，空间和时间复杂度都会非常的大。编写也很困难。

分块就类似于十分简单的线段树

下列代码是基于此题的

构造分块

struct node{    int l;//左端点    int r;//右端点    int tag;//加法标记    int len;//长度，然鹅这里并没有什么卵用};node kuai[1010];    //关于每一个块的结构体int ll;//块的个数void first_work(){    int k=sqrt(double(n));//n为要分块的数列的长度，k为每块的长度。至于为什么是根号下，可以自行百度。我才不会告诉你是因为我太蒟蒻了    for(int i=1;i<=n;i+=k)    {        kuai[++ll].l=i;//左断点赋值        kuai[ll].r=min(n,i+k-1);//右端点赋值        kuai[ll].len=k;//长度        kuai[ll].tag=0;//加法标记        sort(now+kuai[ll].l,now+kuai[ll].r+1,compare);//排序一下，使其具有单调性，这样查找时就可以二分了。                //这里now是被分块的数组名称    }}

对于查询：

如果在整块中就二分查找

如果不在整块中就暴力查找

int viocheck(int num,int left,int right,int val)//暴力查找。val：value{    int re=0;//查找的个数    for(int i=left;i<=right;i++)        if(now[i]+kuai[num].tag>=val)//这里一定要加上tag。因为我写的代码里没有tag下传            re++;    return re;}int quick_check(int num,int val)//二分{    int left=kuai[num].l,right=kuai[num].r//左右端点;    while(left
    
     =val)//对于单点要特判        ans++;    return ans+=left-kuai[num].l;//计算满足条件个数的个数}void output(int x,int y,int val)//输出发答案{    int ans=0;    for(int i=1;i<=ll;i++)    {        if(x<=kuai[i].l&&y>=kuai[i].r)//某一个块被整体包含            ans+=quick_check(i,val);        else    if(x>=kuai[i].l&&y>=kuai[i].r)  ans+=viocheck(i,x,kuai[i].r,val);//没有被整体包含，但是有交集        else    if(x<=kuai[i].l&&y<=kuai[i].r)  ans+=viocheck(i,kuai[i].l,y,val);        else    if(y<=kuai[i].l)    break;//要查询区间的右端点已经在当前块左端点的右边了。    }    printf("%d\n",ans);}
    

对于区间加

如果某一个块被包含就打tag

没有就暴力加，然后维护单调性

void viochange(int num,int left,int right,int val)//暴力加{    for(int i=kuai[num].l;i<=kuai[num].r;i++)        if(i>=left&&i<=right)               now[i]+=val;    sort(now+kuai[num].l,now+kuai[num].r+1,compare);    return ;}void add(int x,int y,int val){    for(int i=1;i<=ll;i++)    {        if(x<=kuai[i].l&&y>=kuai[i].r)            kuai[i].tag+=val;        else    if(x>=kuai[i].l&&y>=kuai[i].r)  viochange(i,x,kuai[i].r,val);        else    if(x<=kuai[i].l&&y<=kuai[i].r)  viochange(i,kuai[i].l,y,val);        else    if(y<=kuai[i].l)    break;//额，同上    }    }

整体代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int sou[10000010],now[10000010];int n,q;struct node{    int l;    int r;    int tag;    int len;};node kuai[1010];int ll;bool compare(const int &a,const int &b){    return a>b;}void first_work(){    int k=sqrt(double(n));    for(int i=1;i<=n;i+=k)    {        kuai[++ll].l=i;        kuai[ll].r=min(n,i+k-1);        kuai[ll].len=k;        kuai[ll].tag=0;        sort(now+kuai[ll].l,now+kuai[ll].r+1,compare);    }}int viocheck(int num,int left,int right,int val){    int re=0;    for(int i=left;i<=right;i++)        if(now[i]+kuai[num].tag>=val)            re++;    return re;}int quick_check(int num,int val){    int left=kuai[num].l,right=kuai[num].r;    while(left
        
         =val)        ans++;    return ans+=left-kuai[num].l;}void output(int x,int y,int val){    int ans=0;    for(int i=1;i<=ll;i++)    {        if(x<=kuai[i].l&&y>=kuai[i].r)            ans+=quick_check(i,val);        else    if(x>=kuai[i].l&&y>=kuai[i].r)  ans+=viocheck(i,x,kuai[i].r,val);        else    if(x<=kuai[i].l&&y<=kuai[i].r)  ans+=viocheck(i,kuai[i].l,y,val);        else    if(y<=kuai[i].l)    break;    }    printf("%d\n",ans);}void viochange(int num,int left,int right,int val){    for(int i=kuai[num].l;i<=kuai[num].r;i++)        if(i>=left&&i<=right)               now[i]+=val;    sort(now+kuai[num].l,now+kuai[num].r+1,compare);    return ;}void add(int x,int y,int val){    for(int i=1;i<=ll;i++)    {        if(x<=kuai[i].l&&y>=kuai[i].r)            kuai[i].tag+=val;        else    if(x>=kuai[i].l&&y>=kuai[i].r)  viochange(i,x,kuai[i].r,val);        else    if(x<=kuai[i].l&&y<=kuai[i].r)  viochange(i,kuai[i].l,y,val);        else    if(y<=kuai[i].l)    break;    }    }int main(){    scanf("%d%d",&n,&q);    for(int i=1;i<=n;i++)    {        scanf("%d",&sou[i]);        now[i]=sou[i];    }    first_work();    char a;    int b,c,d;    for(int i=1;i<=q;i++)    {        cin>>a;        scanf("%d%d%d",&b,&c,&d);        if(a=='A')            output(b,c,d);        if(a=='M')            add(b,c,d);    }}
        
       
      
     
    

en~应该就是这么样了。