『分块』分块入门1-9题解

关于分块

关于分块，其主要思想是大局维护，局部朴素；即吧一个序列分成若干个小块，对任意区间进行操作的时候：如果区间内包含完整块，就进行快速的整体修改；若所修改区间内的一部分是某个个块中的一部分，则直接进行暴力修改就行。根据有关数学知识，可以证明分成$\sqrt{n}$的时间效率最高，一般的时间复杂度则是$O(n\sqrt{n})$

分块入门1

给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。

这道题就是分块一个灰常简单的模板了，具体可以这么做：

设修改的区间为$[l,r]$，此时在分块中预处理了每一个区间的左端点和右端点，当前枚举为第i个区间。若区间$i$在$[l,r]$以内，则直接用数组$add[i]$进行区间的整体操作，表示第$i$个区间的所有数的变化量，只需要累加一次。若区间i的一部分在$[l,r]$以内，暴力修改即可。直接在a数组上修改。对于查询的点x，输出的值为：$a[i]+add[po{s}_i]$,$po{s}_i$表示$i$所属的块的编号。 代码如下：

（注意：代码可能与上述讲解的数组含义有所出入）

例如：上面的add是sum，而下面的add是单点变化量，等同于在原数组上做修改。

#include<bits/stdc++.h> using namespace std; int n,m; int a[100000]; int L[100000]; int R[100000]; int add[100000]; int sum[100000]; int num[100000]; void Plus(int l,int r,int c) { for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) sum[i]+=c; else { for (int j=max(L[i],l);j<=min(R[i],r);++j) add[j]+=c; } } } void ask(int x) { printf("%d\n",a[x]+sum[num[x]]+add[x]); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",a+i); m=sqrt(n); for (int i=1;i<=m;++i) { L[i]=sqrt(n)*(i-1)+1; R[i]=sqrt(n)*i; } if (R[m]<n) { m++; L[m]=R[m-1]+1; R[m]=n; } for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) num[j]=i; for (int i=1,opt,l,r,c;i<=n;++i) { scanf("%d %d %d %d",&opt,&l,&r,&c); if (opt == 0) Plus(l,r,c); if (opt == 1) ask(r); } return 0; }

分块入门2

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。

区间加法的方法同分块1，我们来考虑如何求小于x的元素个数。

对于每一个块，我们可以在一开始分别进行排序，若不进行修改操作就可以直接用二分查找得到答案。

对于区间修改来说，如果是整块的修改则没有关系，因为仍然保证有序性。

如果是两端零零散散的修改，在修改完之后再对这些块分别进行排序。

这个就可以用过二分查找或者lowerbound函数在log的复杂度内解决问题了。

因为分成的块是logn块，时间复杂度是$O(n\sqrt{n}+2\ast \sqrt{n}log\sqrt{n})$

代码如下：

#include<bits/stdc++.h> #define find lower_bound using namespace std; int n,m; int a[100000]; int L[100000]; int R[100000]; int pos[100000]; int sum[100000]; vector<int>num[100000]; void reset(int x) { num[x].clear(); for (int i=L[x];i<=R[x];++i) num[x].push_back(a[i]); sort(num[x].begin(),num[x].end()); } void change(int l,int r,int v) { for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) sum[i]+=v; else { for (int j=max(l,L[i]);j<=min(R[i],r);++j) a[j]+=v; reset(i); } } } void print(int l,int r,int k) { int ans=0; for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) ans += find (num[i].begin(), num[i].end(), k*k-sum[i]) - num[i].begin(); else for (int j=max(l,L[i]);j<=min(R[i],r);++j) if (a[j]+sum[pos[j]]<k*k) ans++; } printf("%d\n",ans); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",a+i); m=sqrt(n); for (int i=1;i<=m;++i) { L[i]=sqrt(n)*(i-1)+1; R[i]=sqrt(n)*i; } if (R[m] < n) { m++; L[m]=R[m-1]+1; R[m]=n; } for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) pos[j]=i; for (int i=1;i<=m;++i) reset(i); for (int i=1,opt,l,r,c;i<=n;++i) { scanf("%d %d %d %d",&opt,&l,&r,&c); if (opt == 0) change(l,r,c); if (opt == 1) print(l,r,c); } return 0; }

分块入门3

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的前驱（比其小的最大元素）。

加法修改和排序和分块2一样，在输出答案的时候需要做一定的修改。

若是整块的区间，则通过lower_bound找到大于等于x的最小值，向后减去1则是小于x的最大值。不完整暴力即可。

代码如下：

#include<bits/stdc++.h> #define find lower_bound using namespace std; int n,m; int a[100000]; int L[100000]; int R[100000]; int pos[100000]; int sum[100000]; vector<int>num[100000]; void reset(int x) { num[x].clear(); for (int i=L[x];i<=R[x];++i) num[x].push_back(a[i]); sort(num[x].begin(),num[x].end()); } void change(int l,int r,int v) { for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) sum[i]+=v; else { for (int j=max(l,L[i]);j<=min(R[i],r);++j) a[j]+=v; reset(i); } } } void print(int l,int r,int k) { int ans=-INT_MAX; for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) { int p=find (num[i].begin() ,num[i].end() ,k-sum[i]) - num[i].begin(); if (p != 0) ans=max(ans,num[i][p-1]+sum[i]); } else { for (int j=max(l,L[i]);j<=min(R[i],r);++j) if (a[j]+sum[i]<k) ans=max(ans,a[j]+sum[i]); } } printf("%d\n",ans == -INT_MAX ? -1 : ans); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",a+i); m=sqrt(n); for (int i=1;i<=m;++i) { L[i]=sqrt(n)*(i-1)+1; R[i]=sqrt(n)*i; } if (R[m] < n) { m++; L[m]=R[m-1]+1; R[m]=n; } for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) pos[j]=i; for (int i=1;i<=m;++i) reset(i); for (int i=1,opt,l,r,c;i<=n;++i) { scanf("%d %d %d %d",&opt,&l,&r,&c); if (opt == 0) change(l,r,c); if (opt == 1) print(l,r,c); } return 0; }

分块入门4

给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。 其实做法和分块1还是一样的，在统计答案的时候改一下就好了。

具体做法如下：

遇到整块修改的，$ad{d}_i+=v$,i表示块的编号，v表示修改量，进行整体修改遇到非整块修改的，$su{m}_{po{s}_i}+=v,a[i]+=v$其中sum表示区间和，a表示原始序列的基础上修改的序列。

遇到查询的时候：

如果是整块的，答案是：$add[i]\ast (R[i]-L[i]+1)+sum[i]$,表示整体修改所增加的值加上暴力修改所增加的值。如果是某一块的一部分，暴力喽。

注意，sum数组在未修改之前也需要预处理。

代码如下：

#include<bits/stdc++.h> #define LL long long using namespace std; LL n,m; LL a[100000]; LL L[100000]; LL R[100000]; LL sum[100000]; LL add[100000]; LL pos[100000]; void change(LL l,LL r,LL c) { for (LL i=1;i<=m;++i) { if (r<L[i] || l>R[i]) continue; if (l<=L[i] && r>=R[i]) add[i]+=c; else for (LL j=max(l,L[i]);j<=min(r,R[i]);++j) sum[i]+=c,a[j]+=c; } } void getans(LL l,LL r,LL P) { LL ans=0; for (LL i=1;i<=m;++i) { if (r<L[i] || l>R[i]) continue; if (l<=L[i] && r>=R[i]) ans+=sum[i]+(R[i]-L[i]+1)*add[i],ans%=P; else for (LL j=max(l,L[i]);j<=min(r,R[i]);++j) ans+=(add[i]+a[j]),ans%=P; } printf("%lld\n",ans); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%lld",&n); for (LL i=1;i<=n;++i) scanf("%lld",a+i); m=sqrt(n); for (LL i=1;i<=m;++i) { L[i]=sqrt(n)*(i-1)+1; R[i]=sqrt(n)*i; } if (R[m]<n) { m++; L[m]=R[m-1]+1; R[m]=n; } for (LL i=1;i<=m;++i) for (LL j=L[i];j<=R[i];++j) sum[i]+=a[j],pos[j]=i; for (LL i=1,opt,l,r,c;i<=n;++i) { scanf("%lld %lld %lld %lld",&opt,&l,&r,&c); if (opt == 0) change(l,r,c); if (opt == 1) getans(l,r,c+1); } return 0; }

分块入门5

给出一个长为n的数列，以及n个操作，操作涉及区间开方，区间求和。

我们发现，当一个数进行若干次开方后会不断在0或1中循环，且开方次数很少，我们便可以利用这一性质来解决此题。

因此对于修改的区间：

如果区间是完整的：如果区间全部变成0/1，跳过；如果不是，则暴力修改。如果是不完整的则暴力修改。

然后暴力用区间和维护即可。

#include<bits/stdc++.h> using namespace std; int n,m; int a[100000]; int L[100000]; int R[100000]; int add[100000]; int pos[100000]; int sum[100000]; int flag[100000]; void sqrtit(int x) { if (flag[x] == 1) return; int flg=1; sum[x]=0; for (int i=L[x];i<=R[x];++i) { a[i]=sqrt(a[i]); sum[x]+=a[i]; if (a[i]>1) flg=0; } flag[x]|=flg; return; } void change(int l,int r) { for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) sqrtit(i); else for (int j=max(l,L[i]);j<=min(r,R[i]);++j) { sum[i]-=a[j]; a[j]=sqrt(a[j]); sum[i]+=a[j]; } } } void getans(int l,int r) { int ans=0; for (int i=1;i<=m;++i) { if (l>R[i] || r<L[i]) continue; if (l<=L[i] && r>=R[i]) ans+=sum[i]; else for (int j=max(l,L[i]);j<=min(r,R[i]);++j) ans+=a[j]; } printf("%d\n",ans); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",a+i); m=sqrt(n); for (int i=1;i<=m;++i) { L[i]=(i-1)*sqrt(n)+1; R[i]=i*sqrt(n); } if (R[m]<n) { m++; L[m]=R[m-1]+1; R[m]=n; } for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) pos[j]=i,sum[i]+=a[j]; for (int i=1,l,r,opt,c;i<=n;++i) { scanf("%d %d %d %d",&opt,&l,&r,&c); if (opt == 0) change(l,r); if (opt == 1) getans(l,r); } return 0; }

分块入门6

给出一个长为n的数列，以及n个操作，操作涉及单点插入，单点询问，数据随机生成。

我们把序列分成$\sqrt{n}$,每次根据查出的位置找到对应的块插入即可。

我们在这里插入使用vector，因为vector支持线性数组的中线插入。

这样的实现复杂度平均好，但是如果某一个块持续插入的话时间复杂度会退化为$O(n^2)$。

我们在这里引入一个新的思想：重构分块。

即如果某一个块的个数超级超级大了，就把当前的所有块解散，然后重新再分；这样就不会被特殊的数据卡了。

代码如下：

#include<bits/stdc++.h> using namespace std; int n,m,now,top; int a[1000000]; int st[1000000]; vector<int>num[1000000]; void again( ) { top=0; for (int i=1;i<=m;++i) { for (int j=0;j<num[i].size();++j) st[++top]=num[i][j]; num[i].clear(); } m=sqrt(top),now=0; for (int i=1;i<=m;++i) for (int j=1;j<=m;++j) num[i].push_back(st[++ now]); if (now < top) { m ++; while (now<top) num[m].push_back(st[++ now]); } } void insert(int l,int r) { int i=1; while (num[i].size()<l) { l-=num[i].size(); i ++; } num[i].insert(num[i].begin()+l-1,r); if (num[i].size()>sqrt(n)*20) again(); } void output(int r) { int i=1; while (r>num[i].size()) { r-=num[i].size(); i ++; } printf("%d\n",num[i][r-1]); } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); scanf("%d",&n); for (int i=1;i<=n;++i) scanf("%d",a+i); m=sqrt(n),now=0; for (int i=1;i<=m;++i) for (int j=1;j<=m;++j) num[i].push_back(a[++ now]); if (now < n) { m ++; while (now<n) num[m].push_back(a[++now]); } for (int i=1,opt,l,r,c;i<=n;++i) { scanf("%d %d %d %d",&opt,&l,&r,&c); if (opt == 0) insert(l,r); if (opt == 1) output(r); } return 0; }

分块入门7

给出一个长为n的数列，以及n个操作，操作涉及区间乘法，区间加法，单点询问。

维护两个标记$(a,b)$,表示原数x经过这两个标记的操作变为$ax+b$.

加法操作，令$(a,b)$变成$(a,b+v).$乘法操作，令$(a,b)$变成$(av,bv)$.

每一次分块，对不完整的块暴力更新一遍。

代码如下：

#include <iostream> #include <cmath> #include <cstdio> #define int long long using namespace std; const int P = 10007; int n,m; int a[200000]; int L[200000]; int R[200000]; int mul[200000]; int inc[200000]; int Pos[200000]; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } void again(int x) { for (int i=L[x];i<=R[x];++i) a[i] = (a[i] * mul[x] + inc[x]) % P; mul[x] = 1, inc[x] = 0; } //分块x累加到具体数值内 void mult(int l,int r,int v) { again(Pos[l]), again(Pos[r]); for (int i=1;i<=m;++i) { if (l > R[i] || r < L[i]) continue; if (l <= L[i] && r >= R[i]) { mul[i] = mul[i] * v % P; inc[i] = inc[i] * v % P; continue; } for (int j=max(L[i],l);j<=min(R[i],r);++j) a[j] = a[j] * v % P; } return; } void Plus(int l,int r,int v) { again(Pos[l]), again(Pos[r]); for (int i=1;i<=m;++i) { if (l > R[i] || r < L[i]) continue; if (l <= L[i] && r >= R[i]) inc[i] = (inc[i] + v) % P; else for (int j=max(L[i],l);j<=min(R[i],r);++j) a[j] = (a[j]+v) % P; } return; } inline int ask(int x) { int ans = a[x] * mul[Pos[x]] + inc[Pos[x]]; return ans % P; } signed main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); n = read(), m = sqrt(n); for (int i=1;i<=n;++i) a[i] = read(); for (int i=1;i<=m;++i) { L[i] = R[i-1]+1; R[i] = i*m; } if (R[m] < n) m ++, L[m] = R[m-1]+1, R[m] = n; for (int i=1;i<=m;++i) { for (int j=L[i];j<=R[i];++j) Pos[j] = i; mul[i] = 1; } for (int i=1;i<=n;++i) { int opt = read(); int l = read(); int r = read(); int c = read(); if (opt == 0) Plus(l,r,c); if (opt == 1) mult(l,r,c); if (opt == 2) printf("%d\n", ask(r)); } return 0; }

分块入门8

给出一个长为n的数列，以及n个操作，操作涉及区间询问等于一个数c的元素，并将这个区间的所有元素改为c。 到最后，几乎每一个区间都是同一个元素；因此对于每一个块来说，颜色相同就直接统计答案，否则暴力扫。我们知道，这样暴力扫每一个块只会被扫一遍。每一次操作得时候把不完整的区间暴力更新即可。

代码如下:

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; int n,m; int ans = 0; int a[200000]; int L[200000]; int R[200000]; int pos[200000]; int tag[200000]; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } void reset(int x,int v) { if (tag[x] == -1) return; for (int i=L[x];i<=R[x];++i) a[i] = tag[x]; tag[x] = -1;//此处一定要坐上标记，因为左边两边的区间在操作后不一定区间都相等 return; } void work(int l, int r, int v) { ans = 0; reset(pos[l],v); if (pos[l] ^ pos[r]) reset(pos[r],v); //对两边已经完全覆盖的区间进行更新 for (int i=1;i<=m;++i) { if (l > R[i] || r < L[i]) continue; if (l <= L[i] && r >= R[i]) { if (tag[i] ^ -1) { if (tag[i] == v) ans += R[i]-L[i]+1; tag[i] = v; continue; } for (int j=L[i];j<=R[i];++j) if (a[j] == v) ans ++; else a[j] = v; tag[i] = v; continue; } for (int j=max(L[i],l);j<=min(R[i],r);++j) if (a[j] == v) ans ++; else a[j] = v; } printf("%d\n", ans); return; } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); memset(tag,-1,sizeof(tag)); n = read(); for (int i=1;i<=n;++i) a[i] = read(); m = sqrt(n); for (int i=1;i<=m;++i) { L[i] = sqrt(n)*(i-1)+1; R[i] = sqrt(n)*i; } if (R[m] < n) m ++, L[m] = R[m-1]+1, R[m] = n; for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) pos[j] = i; for (int i=1;i<=n;++i) { int l = read(), r = read(), c = read(); work(l, r, c); } return 0; }

分块入门9

给出一个长为n的数列，以及n个操作，操作涉及询问区间的最小众数。

首先离散化。求区间众数，则这些数一定是完整块的众数和不完整块的数的其中之一。

我们先预处理完整块的区间众数，我们就可以知道哪些数有可能成为区间众数了。

现在我们考虑数字$x$在区间$[l,r]$中出现了几次。

我们用一个$vector$保存一个数出现的下表，例如数字$2$的下表为$1,3,4,7.$

答案是小于r的最大值的下表-大于等于l最小值的下表。

例如查找$[2,5]$内$2$的个数，显然大于等于$2$的下表为$2$，小于$4$的下表为$3$，答案是$3-2+1=2.$

然后对每一个这样的数字进行二分查找即可。

代码如下：

#include <bits/stdc++.h> using namespace std; int ID = 0; int n,m,T; int L[200000]; int R[200000]; int a[200000]; int pos[200000]; int cnt[200000]; int val[200000]; int MAX[4000][4000]; map <int, int> v; vector <int> h[200000]; inline int read(void) { int s = 0, w = 1;char c = getchar(); while (c<'0' || c>'9') {if (c == '-') w = -1; c = getchar();} while (c>='0' && c<='9') s = s*10+c-48,c = getchar(); return s*w; } void FindMax(int x) { int Max = 0, num = 0; memset(cnt,0,sizeof cnt); for (int i=L[x];i<=n;++i) { int now = pos[i]; cnt[a[i]] ++; if (cnt[a[i]] > Max || cnt[a[i]] == Max && val[a[i]] < val[num]) Max = cnt[a[i]], num = a[i]; MAX[x][now] = num; } return; } void init(void) { n = read(); for (int i=1;i<=n;++i) { a[i] = read(); if (v[a[i]] == 0) v[a[i]] = ++ID, val[ID] = a[i]; a[i] = v[a[i]]; h[a[i]].push_back(i); } T = sqrt(n); m = n/T; for (int i=1;i<=m;++i) L[i] = T*(i-1)+1, R[i] = i*T; if (R[m] < n) m ++, L[m] = R[m-1]+1, R[m] = n; for (int i=1;i<=m;++i) for (int j=L[i];j<=R[i];++j) pos[j] = i; for (int i=1;i<=m;++i) FindMax(i); return; } int query(int x,int l,int r) { int ps1 = lower_bound(h[x].begin(),h[x].end(),l)-h[x].begin(); int ps2 = upper_bound(h[x].begin(),h[x].end(),r)-h[x].begin()-1; return ps2 - ps1 + 1; } void work(void) { int l = read(), r = read(); int num = MAX[pos[l]+1][pos[r]-1]; int Max = query(num,l,r); for (int i=max(l,L[pos[l]]);i<=min(r,R[pos[l]]);++i) { int Cnt = query(a[i],l,r); if (Cnt > Max || Cnt == Max && val[a[i]] < val[num]) Max = Cnt, num = a[i]; } if (pos[l] == pos[r]) { printf("%d\n", val[num]); return; } for (int i=max(l,L[pos[r]]);i<=min(r,R[pos[r]]);++i) { int Cnt = query(a[i],l,r); if (Cnt > Max || Cnt == Max && val[a[i]] < val[num]) Max = Cnt, num = a[i]; } printf("%d\n", val[num]); return; } int main(void) { freopen("a.in","r",stdin); freopen("a.out","w",stdout); init(); int m = n; while (m --) work(); return 0; }