???????

????????作者： hsez_yyh

? ? ? ?鏈接：???????????????https://blog.csdn.net/yyh_getAC/article/details/126823013

? ? ? ?來源：湖北省黃石二中信息競賽組
? ? ? ?著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

????????分塊，顧名思義，就是把問題分成很多塊，然后對每塊單獨求解，最終的答案就是每塊的答案的并。? ? ? ? 在信息學中，我們通常將分塊定義為 把一個長度為 N 的序列分成若干塊，然后對于每次在序列上的操作 ( 一般是區(qū)間的修改和查詢)，我們們分別在操作設計的那些塊上進行即可。 簡單的來說，分塊其實就是一種暴力的優(yōu)化。

? ? ? ? 還是先來看一個小問題：?243. 一個簡單的整數(shù)問題2 - AcWing題庫

? ? ? ? 該題要支持區(qū)間加以及區(qū)間求和，很顯然，這是一個線段樹的板子題，然而我們今天不用線段樹來做。首先我們想一想這道題暴力慢在哪，每次操作如果我們暴力進行的話，那將會是??的復雜度，但是我們好好想一想，每次區(qū)間加法的時候，我們其實是沒必要過多關注每個元素的具體值的，例如我們將區(qū)間 [ l , r ] 這段區(qū)間內(nèi)的所有數(shù)都+1，其實相當于將[ l , r ] 這個區(qū)間內(nèi)所有元素的和+( r-l+1 )，類比于線段樹，要是我們能簡化這個過程就好了，也就是說，我們要是能采取一種非線段樹的方式給每次操作的區(qū)間打上標記(即增刪改了些什么)就好了。? ? ? ? 為了不使用線段樹，并且要使復雜度盡可能的優(yōu)，那就得請出我們今天的主角： 分塊 。

分塊的實現(xiàn)

? ? ? ? 分塊的思路很簡單。 首先，我們先把給定的數(shù)組進行分塊處理，即把他們分成若干個相同的區(qū)間，一般的，我們把每個塊的長度定為??；為什么是 ?呢 ？ 因為我們的操作是基于塊的：? ? ? ? 假設我們當前要操作的區(qū)間為 [ l , r ] ，那么我們可以先看有多少個塊完全處于這個區(qū)間中，對于這些塊，我們將只需要在塊上打上操作標記即可，并不用真正地每個元素修改，而我們最多會有???個塊，所以這個過程的復雜度為??的 ； 特別的我們還會有一些塊只有一部分在我們的區(qū)間中，而根據(jù)常識，這樣的塊最多只會存在兩塊，那么我們對于這兩塊，直接暴力地修改包含在區(qū)間的部分的元素即可，很顯然，這兩塊的元素最多有?? 個，所以過程的復雜度也在?的級別。 而每次操作，我們最壞會把上述的兩個過程都跑滿，但是除去我們小小的常數(shù)，單次操作的復雜度還是可以保證在??級別的。，所以這樣算下來，我們分塊的總復雜度大約為??，雖然不及線段樹，但是速度還是很快的，爆切幾道題目還是可以的。

我們還是畫個圖來感性理解一下，就以上述那道題目為例：

? ? ? ? ?然后我們來進行一個修改操作，比如說把區(qū)間 [ 3,8 ] 內(nèi)的所有元素 + 2?

????????

? ? ? ? ?修改操作非常簡單，我們再來看看查詢操作，例如：求區(qū)間[ 4,8 ] 內(nèi)的元素和：

????????

可見 求和操作也非常的簡單，那么我們就能愉快的切掉例題了：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e5+10; LL a[N]; int loc[N],len,tot; struct node {int l,r;LL sum,tag; // sum為該塊內(nèi)元素和，tag為塊標記 }blk[N]; int n,m; void modify(int l,int r,LL val) //修改操作 {int idx=loc[l],idy=loc[r];if(idx==idy) // 如果區(qū)間只在一個塊內(nèi) ，就暴力更新答案 {for(int i=l;i<=r;i++)a[i]+=val;blk[idx].sum+=val*(r-l+1);}else{ // 先暴力更新不是整塊的部分 for(int i=l;i<=blk[idx].r;i++)a[i]+=val;blk[idx].sum+=val*(blk[idx].r-l+1);for(int i=blk[idy].l;i<=r;i++)a[i]+=val;blk[idy].sum+=val*(r-blk[idy].l+1); for(int i=idx+1;i<idy;i++) //跳塊，直接對于每塊操作 {blk[i].tag+=val;blk[i].sum+=val*(blk[i].r-blk[i].l+1); }} } LL query(int l,int r) // 查詢操作 {int idx=loc[l],idy=loc[r];LL ans=0;if(idx==idy) // 如果區(qū)間只在一個塊內(nèi) ，就暴力統(tǒng)計答案{for(int i=l;i<=r;i++)ans+=(a[i]+blk[idx].tag);return ans;}else{ // 先暴力統(tǒng)計不是整塊的部分 for(int i=l;i<=blk[idx].r;i++)ans+=a[i]+blk[idx].tag;for(int i=blk[idy].l;i<=r;i++)ans+=a[i]+blk[idy].tag;for(int i=idx+1;i<idy;i++) // 然后直接加上所有整塊的塊內(nèi)元素和 ans+=blk[i].sum;return ans;} } int main() {scanf("%d %d",&n,&m);len=sqrt(n); //求出每塊的長度 for(int i=1;i<=n;i++){scanf("%lld",&a[i]);loc[i]=(i-1)/len+1; //求出每個元素屬于哪一個塊 blk[loc[i]].sum+=a[i]; // 預處理塊內(nèi)元素和 if((i-1)%len==0) blk[++tot].l=i; // 這里是記錄每一個塊最左邊的元素的位置if(i%len==0) blk[tot].r=i; // 這里是記錄每一個塊最右邊的元素的位置}char op[2];int xx,yy;LL ff;while(m--){scanf("%s",op);scanf("%d %d",&xx,&yy);if(xx>yy) swap(xx,yy);if(op[0]=='C'){scanf("%lld",&ff);modify(xx,yy,ff);}else printf("%lld\n",query(xx,yy));}return 0; }

可見代碼非常好寫，極其直白，充分體現(xiàn)了暴力美學。

再來看一道題目：Anton and Permutation - 洛谷

題目大意：對于一個長度為 n 的序列進行 k 次操作，每次操作都是交換序列中的某兩個數(shù)。對于每一個操作，回答當前序列中有多少個逆序?qū)Α?/p>

? ? ? ? 這乍一看還真沒思路，再仔細想想，emmm，這不是樹套樹嘛。? ? ? ? 其實完全不用，我們可以用分塊愉快的水過去，空間消耗還少了不知道多少。? ? ? ? 根據(jù)一波玄學分析可以發(fā)現(xiàn)，假設我們要交換 l 和 r 這兩個位置上的元素，即swap( a[l],a[r] ) ，其影響到的逆序?qū)Φ膫€數(shù)只會和在區(qū)間? [ l, r ] 中值域在[ min(a[l],a[r]),max(a[l],a[r]) ] 中的數(shù)；這樣，我們又將其轉(zhuǎn)換成了一個區(qū)間問題：我們先分塊，然后對每個塊分別排序，然后在操作時直接二分出該塊內(nèi)有多少個數(shù)在上述值域中即可。然后對于只有部分在區(qū)間中的塊，直接暴力統(tǒng)計答案即可。總復雜度 ：?還是可以接受的。? ? ? ? 代碼：

????????

#include<bits/stdc++.h> #pragma optimize("Ofast") using namespace std; typedef long long LL; const int N=2e5+10,M=501; int n,q; int loc[N],len,a[N]; struct node {int l,r,id; }blk[M]; vector<int> v[M]; LL solve(int l,int r) {if(l==r) return 0;int idx,idy,xx,yy,k;xx=a[l],yy=a[r];idx=loc[xx],idy=loc[yy];k=find(v[idx].begin(),v[idx].end(),xx)-v[idx].begin();v[idx][k]=yy; loc[yy]=idx;sort(v[idx].begin(),v[idx].end());k=find(v[idy].begin(),v[idy].end(),yy)-v[idy].begin();v[idy][k]=xx; loc[xx]=idy;sort(v[idy].begin(),v[idy].end());LL ans=0,f;if(xx>yy) f=-1,swap(xx,yy);else f=1;if(idx==idy){for(int i=l+1;i<=r-1;i++)if(xx<a[i]&&a[i]<yy) ans++;}else{for(int i=l+1;i<=blk[idx].r;i++)if(xx<a[i]&&a[i]<yy) ans++;for(int i=blk[idy].l;i<=r-1;i++)if(xx<a[i]&&a[i]<yy) ans++;for(int i=idx+1;i<idy;i++)ans+=lower_bound(v[i].begin(),v[i].end(),yy)-upper_bound(v[i].begin(),v[i].end(),xx);}swap(a[l],a[r]);return (2*ans+1)*f; } int main() {scanf("%d %d",&n,&q);len=sqrt(n);int tot=0;for(int i=1;i<=n;i++){a[i]=i;loc[i]=(i-1)/len+1;v[loc[i]].push_back(i);if((i-1)%len==0) blk[++tot].l=i;if(i%len==0) blk[tot].r=i;}long long ans=0;while(q--){int l,r;scanf("%d %d",&l,&r);if(l>r) swap(l,r);ans+=solve(l,r);printf("%lld\n",ans);}return 0; }

? ? ? ? 再再再看一道題：作詩 - 洛谷

題目大意：求區(qū)間內(nèi)出現(xiàn)偶數(shù)次數(shù)的數(shù)個數(shù)。? ? ? ? 嗯，可以莫隊，但是，強制在線，好了，只能考慮分塊了。。。

? ? ? ? 我們直接預處理出每塊到每塊的答案，然后再把每個數(shù)在每一塊內(nèi)出現(xiàn)的個數(shù)求出來，用塊前綴和處理，就可以輕松切掉了。

? ? ? ? 代碼：

#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=320; int n,m,c,tot; int loc[N],a[N]; int cnt[M][N],f[M][N],len; struct node {int l,r,id; }blk[M]; int num[N],st[N]; int ans=0; void solve(int l,int r) {int top=0;if(loc[l]==loc[r]){for(int i=l;i<=r;i++){num[a[i]]++;st[++top]=a[i];}while(top){if(num[st[top]]!=0){ans+=(num[st[top]]&1)^1;num[st[top]]=0;}top--;}return ;}else{if(loc[l]<loc[r]-1) ans=f[loc[l]+1][loc[r]-1];int idx=loc[l],idy=loc[r];for(int i=l;i<=blk[idx].r;i++){num[a[i]]++;st[++top]=a[i];}for(int i=blk[idy].l;i<=r;i++){num[a[i]]++;st[++top]=a[i];}while(top){int t=st[top];if(num[t]!=0&&t!=0){int u=cnt[idx+1][t]-cnt[idy][t];if((u%2)&&(num[t]%2)) ans++;else if(u==0&&num[t]%2==0) ans++;else if(u>0&&u%2==0&&num[t]%2) ans--;num[t]=0;}top--;}} } int main() {scanf("%d %d %d",&n,&c,&m);len=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);loc[i]=(i-1)/len+1;if((i-1)%len==0) blk[++tot].l=i;if(i%len==0) blk[tot].r=i;}blk[tot].r=n;for(int i=1;i<=n;i+=len){int di=loc[i];int t=0;for(int j=i;j<=n;j++){cnt[di][a[j]]++;if((cnt[di][a[j]]&1)&&(cnt[di][a[j]]>1)) t--;else if((cnt[di][a[j]]&1)==0) t++;if(j==n) f[di][loc[j]]=t;else if(j%len==0) f[di][loc[j]]=t; }}int l,r;while(m--){scanf("%d %d",&l,&r);l=((l+ans)%n)+1,r=((r+ans)%n)+1;if (l>r) swap(l,r);ans=0;solve(l,r);printf("%d\n",ans);}return 0; }

????????

? ? ? ? 好的，還有幾道分塊的題目可以做一下：

????????[Violet]蒲公英 - 洛谷? ? ? ? 求區(qū)間眾數(shù)，沒有修改但是強制在線，可以先預處理每塊內(nèi)每種蒲公英出現(xiàn)的數(shù)量，然后求塊前綴和，在預處理出任意兩個塊的眾數(shù)。? ? ? ? 我們詢問 [ l,r ] 這個區(qū)間，其區(qū)間眾數(shù)肯定是區(qū)間中完整的塊的眾數(shù)和其他部分中出現(xiàn)次數(shù)最多的數(shù)中的一個。這樣，我們就可以得到??個可能答案，然后我們只需要在這個答案中找出最大的那一個即可，然后對于每一個可能答案，我們可以的統(tǒng)計，那么總復雜度為：??；由于數(shù)據(jù)較大，我們需要先離散化。

????????

#include<bits/stdc++.h> using namespace std; const int N=4e4+10,M=210; int n,m,tot; int loc[N],len; struct node {int l,r,id; }blk[M]; int a[N],c[N]; vector<int> v[N]; int d[M][M]; int get_num(int &l,int &r,int &k) {return upper_bound(v[k].begin(),v[k].end(),r)-lower_bound(v[k].begin(),v[k].end(),l); } int solve(int l,int r) {int ans=0;int idx=loc[l],idy=loc[r];if(idx<idy-1) ans=d[idx+1][idy-1];int nn=get_num(l,r,ans),n1;if(idx==idy){for(int i=l;i<=r;i++){n1=get_num(l,r,a[i]);if(nn<n1||(nn==n1&&a[i]<ans)) ans=a[i],nn=n1;}}else{for(int i=l;i<=blk[idx].r;i++){n1=get_num(l,r,a[i]);if(nn<n1||(nn==n1&&a[i]<ans)) ans=a[i],nn=n1;}for(int i=blk[idy].l;i<=r;i++){n1=get_num(l,r,a[i]);if(nn<n1||(nn==n1&&a[i]<ans)) ans=a[i],nn=n1;}}return c[ans]; } int main() {scanf("%d %d",&n,&m);len=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);loc[i]=(i-1)/len+1;if((i-1)%len==0) blk[++tot].l=i;if(i%len==0) blk[tot].r=i;c[i]=a[i];}sort(c+1,c+1+n);for(int i=1;i<=n;i++){a[i]=lower_bound(c+1,c+1+n,a[i])-c;v[a[i]].push_back(i);}int cnt[N],res;for(int i=1;i<=n;i+=len){memset(cnt,0,sizeof(cnt));res=0;for(int j=i;j<=n;j++){cnt[a[j]]++;if(cnt[a[j]]>cnt[res]||(cnt[a[j]]==cnt[res]&&a[j]<res)) res=a[j];if(j%len==0) d[(i-1)/len+1][j/len]=res;else if(j==n) d[(i-1)/len+1][j/len+1]=res;}}int last=0,l,r;while(m--){scanf("%d %d",&l,&r);l=(l+last-1)%n+1;r=(r+last-1)%n+1;if(l>r) swap(l,r);last=solve(l,r);printf("%d\n",last);}return 0; }

其實如果用差分統(tǒng)計答案的話，復雜度能降一個??。

????????簡單的問題(easy) - 洛谷? ? ? ? 詢問區(qū)間所有奇數(shù)中最大的那一個，每次把某個區(qū)間中所有的數(shù)加上同一個值，直接分塊，此題比較水，每塊維護該塊內(nèi)最大的奇數(shù)和最大的偶數(shù)即可，要開O2。

? ? ? ? 代碼如下：

????????

#include<bits/stdc++.h> using namespace std; template<typename T>inline void read(T &FF){T RR=1;FF=0;char CH=getchar();for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);FF*=RR; } typedef long long LL; const int N=2e5+10; int n,q,loc[N]; struct node {int l,r;int id,si[2];LL mx[2],add; }blk[502]; LL a[N],mm; int len,tot,sum=0; void modify(int l,int r,LL val) {int idx=loc[l],idy=loc[r];if(idx==idy){for(int i=l;i<=r;i++) a[i]+=val;blk[idx].si[1]=blk[idx].si[0]=0;blk[idx].mx[1]=blk[idx].mx[0]=0;for(int i=blk[idx].l;i<=blk[idx].r;i++){a[i]+=blk[idx].add;if(a[i]%2LL){blk[loc[i]].mx[1]=max(blk[loc[i]].mx[1],a[i]);blk[loc[i]].si[1]++;}else{blk[loc[i]].mx[0]=max(blk[loc[i]].mx[0],a[i]);blk[loc[i]].si[0]++;}}blk[idx].add=0;}else{for(int i=idx+1;i<=idy-1;i++){if(blk[i].si[1])blk[i].mx[1]+=val;if(blk[i].si[0])blk[i].mx[0]+=val;if(val%2LL){swap(blk[i].si[0],blk[i].si[1]);swap(blk[i].mx[1],blk[i].mx[0]);}blk[i].add+=val;}for(int i=l;i<=blk[idx].r;i++) a[i]+=val;for(int i=blk[idy].l;i<=r;i++) a[i]+=val;blk[idx].si[1]=blk[idx].si[0]=blk[idy].si[1]=blk[idy].si[0]=0;blk[idx].mx[1]=blk[idx].mx[0]=blk[idy].mx[1]=blk[idy].mx[0]=0;for(int i=blk[idx].l;i<=blk[idx].r;i++){a[i]+=blk[idx].add;if(a[i]%2LL){blk[loc[i]].mx[1]=max(blk[loc[i]].mx[1],a[i]);blk[loc[i]].si[1]++;}else{blk[loc[i]].mx[0]=max(blk[loc[i]].mx[0],a[i]);blk[loc[i]].si[0]++;}}blk[idx].add=0;for(int i=blk[idy].l;i<=blk[idy].r;i++){a[i]+=blk[idy].add;if(a[i]%2LL){blk[loc[i]].mx[1]=max(blk[loc[i]].mx[1],a[i]);blk[loc[i]].si[1]++;}else{blk[loc[i]].mx[0]=max(blk[loc[i]].mx[0],a[i]);blk[loc[i]].si[0]++;}}blk[idy].add=0;} } void query(int l,int r) {int idx=loc[l],idy=loc[r];sum=0,mm=0;if(idx==idy){for(int i=l;i<=r;i++){if((a[i]+blk[idx].add)%2LL){sum++;mm=max(mm,a[i]+blk[idx].add);} }return ;}else{for(int i=idx+1;i<=idy-1;i++){sum+=blk[i].si[1];mm=max(mm,blk[i].mx[1]);}for(int i=l;i<=blk[idx].r;i++){if((a[i]+blk[idx].add)%2LL){sum++;mm=max(mm,a[i]+blk[idx].add);}}for(int i=blk[idy].l;i<=r;i++){if((a[i]+blk[idy].add)%2LL){sum++;mm=max(mm,a[i]+blk[idy].add);}}}return ; } int main() {read(n);len=sqrt(n);for(int i=1;i<=n;i++){loc[i]=(i-1)/len+1;read(a[i]);if((i-1)%len==0) blk[++tot].l=i;if(i%len==0) blk[tot].r=i;if(a[i]%2LL){blk[loc[i]].mx[1]=max(blk[loc[i]].mx[1],a[i]);blk[loc[i]].si[1]++;}else{blk[loc[i]].mx[0]=max(blk[loc[i]].mx[0],a[i]);blk[loc[i]].si[0]++;}}read(q);int op,l,r;LL xx;while(q--){read(op),read(l),read(r);if(op==1){query(l,r);printf("%d %lld\n",sum,mm);}else{read(xx);modify(l,r,xx);}}return 0; }

????????

? ? ? ? 好了，分塊就講到這里了，希望大家能牢記這個數(shù)據(jù)結(jié)構(gòu)，其可能會出其不意地幫你A掉許多很困難的題目。

總結(jié)

以上是生活随笔為你收集整理的分块详解(优雅的暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。