引
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
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※台北網頁設計公司全省服務真心推薦
※想知道最厲害的網頁設計公司"嚨底家"!
※推薦評價好的iphone維修中心