从疫情中的体温测量到分块思想的运用

引

Once upon a time，COVID-19席卷全球，Chinese Government要求学校复课时必须测量学生体温

YC中学有几万名同学，要找到发烧的同学进行隔离 如果要让一位老师完成所有测温任务，那这将是一个大工程，效率会很低（左图）

所以将学校所有同学分成班级进行，然后汇总，效率会更高（右图）

介

刚刚 引 中我们说的：

将学校所有同学分成班级进行，然后汇总

这就是一种分块

那问题来了，什么是分块呢？

其实通过刚刚的情景，你已经领悟到了分块的本质：

将一个整体划分为若干个小块，进行处理

算法中，与之对应的就是：

详

总

那么，分块到底是怎么一种思想呢？

整块维护，残块查找

例

还是以测量体温举例：

现在YC中学要查找体温在36℃~37.5℃区间内的同学

怎么做呢？

不可能又去挨个同学去统计、去数吧

那就做一张大表吧，在之前测温的时候就把34 ~ 35℃、35 ~36℃、36 ~ 37℃、37 ~ 38℃、38 ~ 39℃……的同学分别列出来，数量分别加出来

然后36 ~ 37℃可以就直接在表里查出人数

那37 ~ 37.5℃怎么办呢？

表内并没有37 ~ 37.5℃的这样0.5大小的区间啊

那就在37 ~ 38℃这个区间去找呗

方法可以直接暴力遍历，也可以二分查找等等

刚刚解决的问题就是一个典型的分块

像34 ~ 35℃、35 ~36℃、36 ~ 37℃、37 ~ 38℃、38 ~ 39℃这种列在表上给出的就是整块

37 ~ 37.5℃这种表上没有，包含在一个其他整块中的但又不足一个整块的就叫做残块

优

不难发现，其实分块这个思想是一种暴力，一种优化的暴力，但往往也很有效

Such as线段树过于臃肿，代码冗长，大材小用；而直接暴力就会TLE，不能满足数据大小

这就很适合分块了

那么我们 具体怎么做 呢？

分

我们先要求得应该分为多少个区块嘛，然后求得每个区块应该包含多少个元素

然后在输入时分块

要使情况最优，那么区块既 不能太少也不能太多

太少，整块的数量会太少，花费大量的时间处理残块

太多，区块的长度会太短，失去整体处理区块的意义

所以，我们取块数为 根号n

而开平方开不尽的n，我们通常在最后接一个不足整块元素的假整块（可以看做整块）

这样在 最坏情况下

我们要处理接近 根号n 个 整块 ，还要对长度为 2倍根号n 的残块最后单独处理

cin>>n;
    blo=sqrt(n);//sqrt()开平方函数
    for(int i=1;i>a[i];//储存元素a[i]
        pos[i]=(i-1)/blo+1;//pos[i]为记录元素a[i]属于第几个整块
        m[pos[i]]=max(a[i],m[pos[i]]);//寻找第pos[i]个整块的最大值存入m[pos[i]]
    }

统

我们先统计左右残块，然后再统计整块

cin>>q;
    int l,r;
    while(q--){
        cin>>l>>r;
        l++;
        r++;
        int ans=0;
        for(int i=l;i<=min(r, pos[l]*blo);i++){//统计左残缺块 
            ans=max(ans,a[i]);
        } 
        if(pos[l]!=pos[r]){//存在右残缺块 
            for(int i=(pos[r]-1)*blo+1;i<=r;i++){//统计右残缺块 
                ans=max(ans,a[i]);
            }
        } 
        for( int i=pos[l]+1;i<=pos[r]-1;i++){//统计中间整块 
            ans=max(ans,m[i]);
        }   
        cout<<ans<<endl;
    }

分块入门之求最大值

先看一个例题

分块入门之求最大值

Input

第一行给出一个数字N，接下来N+1行，每行给出一个数字Ai，（1<=i<=N<=1E5)

接来给出一个数字Q(Q<=7000),代表有Q个询问

每组询问格式为a,b即询问从输入的第a个数到第b个数，其中的最大值是多少

Output

如题所述

Sample Input

10 0 1 2 3 2 3 4 3 2 1 0 5 0 10 2 4 3 7 7 9 8 8

Sample Output

4 3 4 3 2

坑

模板题，然后刚刚已经讲过了这个代码

唯一的坑就在于 接下来N+1行 都是 数字Ai

也就是有 n+1 个 数字Ai

也就是n需要n++

码

#include 
using namespace std;
int n;
int a[101000];
int q;
int blo;
int pos[101000];
int m[101000];
//blo为区间大小，pos[i]表示a[i]元素位于第pos[i]块，m[i]表示区块最大值
int main(){
    cin>>n;
    n++;
    blo=sqrt(n);
    for(int i=1;i>a[i];
        pos[i]=(i-1)/blo+1;
        m[pos[i]]=max(a[i],m[pos[i]]);
    }
    cin>>q;
    int l,r;
    while(q--){
        cin>>l>>r;
        l++;
        r++;
        int ans=0;
        for(int i=l;i<=min(r, pos[l]*blo);i++){//统计左残缺块 
            ans=max(ans,a[i]);
        } 
        if(pos[l]!=pos[r]){//存在右残缺块 
            for(int i=(pos[r]-1)*blo+1;i<=r;i++){//统计右残缺块 
                ans=max(ans,a[i]);
            }
        } 
        for( int i=pos[l]+1;i<=pos[r]-1;i++){//统计中间整块 
            ans=max(ans,m[i]);
        }   
        cout<<ans<<endl;
    }
    return 0;
}

教主的魔法

[Noip模拟题]教主的魔法

Description

教主最近学会了一种神奇的魔法，能够使人长高

于是他准备演示给XMYZ信息组每个英雄看

于是N个英雄们又一次聚集在了一起

这次他们排成了一列，被编号为1、2、……、N

每个人的身高一开始都是不超过1000的正整数

教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W

（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高）

CYZ、光哥和ZJQ等人不信教主的邪

于是他们有时候会问WD闭区间 [L,R] 内有多少英雄身高大于等于C

以验证教主的魔法是否真的有效

WD巨懒，于是他 把这个回答的任务交给了你

Input

第1行为两个整数N、Q。Q为问题数与教主的施法数总和

第2行有N个正整数，第i个数代表第i个英雄的身高

第3到第Q+2行每行有一个操作：

（1）若第一个字母为”M”，则紧接着有三个数字L、R、W

表示对闭区间 [L, R]内所有英雄的身高加上W

（2）若第一个字母为”A”，则紧接着有三个数字L、R、C

询问闭区间 [L, R] 内有多少英雄的身高大于等于C

N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000

Output

对每个”A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。Sample Input

5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4

Sample Output

2 3

【输入输出样例说明】

原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4

教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4

意

很多元素，进行增加、查找最大值操作

修

多了一个 修改操作 ，不是很难

同理像查找这样 整块维护，残块增加

我们就再 增加一个数组 ，统一记录 每个整块变化量 是多少

记录每个整块的变化量，然后最后 找最值 的时候， 单个整块的最值 加上或者减去变化量比较就可以了

残块的单个元素就 直接加上或者减去 变化量， 找最值

void update(int x,int y,int v){
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++)a[i]=a[i]+v;
    }
    else{
        for(int i=x;i<=pos[x]*block;i++)a[i]=a[i]+v;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]=a[i]+v;
    }
    reset(pos[x]);reset(pos[y]);
    for(int i=pos[x]+1;i<pos[y];i++)
       add[i]+=v;
}

码

#include
using namespace std;
int n;
int q,m,block;
int a[1010000],b[1010000],pos[1010000],add[1010000];
void reset(int x){
    int l=(x-1)*block+1,r=min(x*block,n);
    for(int i=l;i<=r;i++)
        b[i]=a[i];
    sort(b+l,b+r+1);
}
int find(int x,int v){
    int l=(x-1)*block+1,r=min(x*block,n);
    int last=r;
    while(l>1;
        if(b[mid]<v)l=mid+1;
        else r=mid-1;
    }
    return last-l+1;
}
void update(int x,int y,int v){
    if(pos[x]==pos[y]){
        for(int i=x;i<=y;i++)a[i]=a[i]+v;
    }
    else{
        for(int i=x;i<=pos[x]*block;i++)a[i]=a[i]+v;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)a[i]=a[i]+v;
    }
    reset(pos[x]);reset(pos[y]);
    for(int i=pos[x]+1;i<pos[y];i++)
       add[i]+=v;
}
int query(int x,int y,int v){
    int sum=0;
    if(pos[x]==pos[y]){
        for(int i=x;i=v)sum++;
    }
    else {
        for(int i=x;i=v)sum++;
        for(int i=(pos[y]-1)*block+1;i=v)sum++;
    }
    for(int i=pos[x]+1;i>n>>q;
    block=int(sqrt(n));
    for(int i=1;i>a[i];
        pos[i]=(i-1)/block+1;
        b[i]=a[i];
    }
    if(n%block)m=n/block+1;
    else m=n/block;
    for(int i=1;i<=m;i++)reset(i);
    for(int i=1;i>ch>>x>>y>>v;
        if(ch[0]=='M'){
            update(x,y,v);
        }else{
            cout<<query(x,y,v)<<endl;
        }
    }
    return 0;
}

END