• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

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

开发技术 开发技术 4周前 (06-19) 28次浏览

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<=n;i++){
		cin>>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 <bits/stdc++.h>
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<=n;i++){
		cin>>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<bits/stdc++.h>
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<=r){
        int mid=(l+r)>>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<=y;i++)if(a[i]+add[pos[i]]>=v)sum++;
    }
    else {
        for(int i=x;i<=pos[x]*block;i++)
            if(a[i]+add[pos[i]]>=v)sum++;
        for(int i=(pos[y]-1)*block+1;i<=y;i++)
            if(a[i]+add[pos[i]]>=v)sum++;
    }
    for(int i=pos[x]+1;i<pos[y];i++)
        sum+=find(i,v-add[i]);
    return sum;
}
int main(){
    cin>>n>>q;
    block=int(sqrt(n));
    for(int i=1;i<=n;i++){
        cin>>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<=q;i++){
        char ch[5];int x,y,v;
        cin>>ch>>x>>y>>v;
        if(ch[0]=='M'){
        	update(x,y,v);
		}else{
			cout<<query(x,y,v)<<endl;
		}
    }
    return 0;
}

END


喜欢 (0)