前言
分塊是一種拓展性比較強的數據結構，對于一些難以合并的區間信息，線段樹處理起來比較棘手（如區間眾數），但是分塊以其靈活的特點能夠較快且直觀地處理
本次筆記主要以hzwer的九道分塊練習題與博客為主
hzwer介紹分塊的博客:http://hzwer.com/8053.html
hzwer的分塊練習題:https://loj.ac/problems/search?keyword=%E5%88%86%E5%9D%97
區間加法&區間求和
應該算最為基礎的一種問題模型了，用其他數據結構當然能很快地解決，不過我們用這個讓大家知道分塊的原理.
首先我們要知道"分塊"，顧名思義，就是把一些信息分成一塊一塊來處理，于是對于一個區間上的信息修改或查詢，這個區間可能既覆蓋了一些整塊，左右兩邊又還有一些多出來的部分，或者區間比較小被一個整塊給覆蓋。
這就給我們處理的思路，對于被區間覆蓋的整塊，直接對這個整塊的信息進行操作，兩邊多出來零散的部分呢就直接暴力處理。當然還有種情況就是如果區間被一個整塊覆蓋，也直接對區間暴力處理。這樣的話設序列大小為\(N\),詢問次數為\(Q\),塊的大小為\(\sqrt N\),時間復雜度就為\(O((N+Q)\sqrt N)\)
代碼方面個人認為lyd的更簡潔易懂,但實際上與hzwer的本質是相同的
\(lydrainbowcat\)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#define ll long long
#define ri register int
using namespace std;
const int maxn=50005;
const int inf=0xfffffff;
template <class T>inline void read(T &x){x=0;int ne=0;char c;while(!isdigit(c=getchar()))ne=c=='-';x=c-48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
int n,size;
int L[maxn],R[maxn],pos[maxn]; //L，R-每個塊的左右端點；pos-元素所在塊的編號
ll sum[maxn],tag[maxn],a[maxn];//sum-塊的和 tag塊的標記 a-元素（序列） 注意開long long
inline void add(int l,int r,int c){int p=pos[l],q=pos[r]; if(p==q){for(ri i=l;i<=r;i++){a[i]+=c;}sum[p]+=(r-l+1)*c;}else{for(ri i=p+1;i<=q-1;i++){tag[i]+=c;}for(ri i=l;i<=R[p];i++)a[i]+=c;sum[p]+=(R[p]-l+1)*c;for(ri i=L[q];i<=r;i++)a[i]+=c;sum[q]+=(r-L[q]+1)*c;}
}
inline ll query(int l,int r){int p=pos[l],q=pos[r];ll ans=0;if(p==q){for(ri i=l;i<=r;i++)ans+=a[i];ans+=tag[p]*(r-l+1);}else{for(ri i=p+1;i<=q-1;i++)ans+=sum[i]+tag[i]*(R[i]-L[i]+1);for(ri i=l;i<=R[p];i++)ans+=a[i]+tag[p];for(ri i=L[q];i<=r;i++)ans+=a[i]+tag[q];}return ans;
}
int main(){read(n);size=sqrt(n);for(ri i=1;i<=n;i++){read(a[i]);}for(ri i=1;i<=size;i++){L[i]=(i-1)*size+1; //標記每個塊的左右端點位置 R[i]=i*size;}if(R[size]<n){size++;L[size]=R[size-1]+1,R[size]=n;}//如果沒湊齊就加一個塊 for(ri i=1;i<=size;i++){for(ri j=L[i];j<=R[i];j++){pos[j]=i;sum[i]+=a[j];}}int op,l,r,c;for(ri i=1;i<=n;i++){read(op),read(l),read(r),read(c);if(!op){add(l,r,c);}else printf("%d\n",query(l,r)%(c+1));}return 0;
}
\(hzwer\)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#define ll long long
#define ri register int
using namespace std;
const int maxn=50005;
const int inf=0xfffffff;
template <class T>inline void read(T &x){x=0;int ne=0;char c;while(!isdigit(c=getchar()))ne=c=='-';x=c-48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
int n;
int blo[maxn],block;
ll sum[maxn],a[maxn],tag[maxn];//類似定義
inline void add(int l,int r,int c){for(ri i=l;i<=min(blo[l]*block,r);i++){//處理最左邊的塊，blo[l]*block其實就是l塊的右端點 a[i]+=c;sum[blo[i]]+=c;}if(blo[l]!=blo[r]){//如果 左右端點不在同一個塊上 for(ri i=(blo[r]-1)*block+1;i<=min(r,n);i++){//處理最右塊，(blo[r]-1)*block+1其實就是r塊的左端點 a[i]+=c;sum[blo[i]]+=c;}}for(ri i=blo[l]+1;i<=blo[r]-1;i++){//處理整塊 sum[i]+=block*c;tag[i]+=c;}
}
inline ll query(int l,int r,int p){ll ans=0;for(ri i=l;i<=min(blo[l]*block,r);i++){ans+=a[i]+tag[blo[i]];}if(blo[l]!=blo[r]){for(ri i=(blo[r]-1)*block+1;i<=min(r,n);i++){ans+=a[i]+tag[blo[i]];}}for(ri i=blo[l]+1;i<=blo[r]-1;i++){ans+=sum[i];}return ans;
}
int main(){read(n);block=sqrt(n);for(ri i=1;i<=n;i++){read(a[i]);blo[i]=(i-1)/block+1;sum[blo[i]]+=a[i];}int op,l,r,c;for(ri i=1;i<=n;i++){read(op),read(l),read(r),read(c);if(!op)add(l,r,c);else printf("%d\n",query(l,r,c+1)%(c+1));}return 0;
}
#pragma GCC optimize(3)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <vector>
#include <map>
#include <queue>
#define ri register int
#define ll long long
using namespace std;
const int inf=0xfffffff;
const int maxn=50005;
int a[maxn],blo[maxn],tag[maxn],block,c;
vector <int> g[maxn];
int n;
template <class T>inline void read(T &x){x=0;int ne=0;char c;while(!isdigit(c=getchar()))ne=c=='-';x=c-48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
inline void reset_block(int now){//重構g[now].clear();for(ri i=(now-1)*block+1;i<=min(now*block,n);i++){g[now].push_back(a[i]);}sort(g[now].begin(),g[now].end());
}
inline void add(int l,int r){for(ri i=l;i<=min(blo[l]*block,r);i++){a[i]+=c;}reset_block(blo[l]);if(blo[l]!=blo[r]){for(ri i=(blo[r]-1)*block+1;i<=r;i++){a[i]+=c;}reset_block(blo[r]);}for(ri i=blo[l]+1;i<=blo[r]-1;i++){tag[i]+=c;}
}
inline int query(int l,int r,int x){int cnt=0;for(ri i=l;i<=min(blo[l]*block,r);i++){if(a[i]+tag[blo[i]]<x)cnt++;}if(blo[l]!=blo[r]){for(ri i=(blo[r]-1)*block+1;i<=min(r,n);i++){if(a[i]+tag[blo[i]]<x)cnt++;}}int tmp;for(ri i=blo[l]+1;i<=blo[r]-1;i++){tmp=lower_bound(g[i].begin(),g[i].end(),x-tag[i])-g[i].begin();cnt+=tmp;}return cnt;
}
int main(){read(n);block=sqrt(n);for(ri i=1;i<=n;i++){read(a[i]);blo[i]=(i-1)/block+1;g[blo[i]].push_back(a[i]);}for(ri i=1;i<=blo[n];i++){sort(g[i].begin(),g[i].end());}int op,l,r;for(ri i=1;i<=n;i++){read(op),read(l),read(r),read(c);if(!op){add(l,r);}else{printf("%d\n",query(l,r,c*c));}}return 0;
}
區間加法&區間前驅
\(X\)的前驅就是小于\(X\)的最大數，用上面那題類似的思路，整塊中二分，左右散塊修改后重構，查詢時暴力查詢
然而hzwer大佬用了set,可是我已經對set的常數產生了心理陰影（相對其他STL），同時LOJ討論區中有人說set可以被hack，感興趣的可以看一看set寫法,這里給出的還是vector二分解法，同時注意tag對操作的影響
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#define ri register int
#define ll long long
using namespace std;
const int inf=0xfffffff;
const int maxn=100005;
template <class T>inline void read(T &x){x=0;int ne=0;char c;while(!isdigit(c=getchar()))ne=c=='-';x=c-48;while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
int n;
int blo[maxn],block,tag[maxn],a[maxn];
vector <int>g[maxn];
inline void reset_block(int now){g[now].clear();for(ri i=(now-1)*block+1;i<=min(now*block,n);i++){g[now].push_back(a[i]);}sort(g[now].begin(),g[now].end());
}
inline void add(int l,int r,int c){for(ri i=l;i<=min(blo[l]*block,r);i++){a[i]+=c;}reset_block(blo[l]);if(blo[l]!=blo[r]){for(ri i=(blo[r]-1)*block+1;i<=min(r,n);i++){a[i]+=c;}reset_block(blo[r]);}for(ri i=blo[l]+1;i<=blo[r]-1;i++){tag[i]+=c;}
}
inline int query(int l,int r,int x){int ans=-inf;for(ri i=l;i<=min(blo[l]*block,r);i++){if(a[i]+tag[blo[i]]<x)ans=max(a[i]+tag[blo[i]],ans);}if(blo[l]!=blo[r]){for(ri i=(blo[r]-1)*block+1;i<=min(r,n);i++){if(a[i]+tag[blo[i]]<x)ans=max(a[i]+tag[blo[i]],ans);}}int tmp=0;for(ri i=blo[l]+1;i<=blo[r]-1;i++){tmp=lower_bound(g[i].begin(),g[i].end(),x-tag[i])-g[i].begin();if(tmp!=0)ans=max(ans,g[i][tmp-1]+tag[i]);//注意這里要加上標記 }if(ans==-inf)ans=-1;return ans;
}
int main(){read(n);block=sqrt(n);for(ri i=1;i<=n;i++){read(a[i]);blo[i]=(i-1)/block+1;g[blo[i]].push_back(a[i]);}for(ri i=1;i<=blo[n];i++){sort(g[i].begin(),g[i].end());}int op,l,r,c;for(ri i=1;i<=n;i++){read(op),read(l),read(r),read(c);if(!op){add(l,r,c);}else{printf("%d\n",query(l,r,c));}}return 0;
}
轉載于:https://www.cnblogs.com/Rye-Catcher/p/9194001.html
總結
以上是生活随笔為你收集整理的学习笔记--分块的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
