当前位置：首页 > news >正文

浅谈根号分治

news 2025/9/21 21:49:52

本文章同步发表在洛谷博客。

什么是根号分治？

根号分治。听起来好像是一个很高级的什么递归做法，但实质上。它，只是一个暴力缝合怪而已。仅此而已。

根号分治很简单的。其实，就是解决一个题目有两种暴力方法，第一种方法的时间复杂度是 \(O(k)\)，第二种方法的时间复杂度则是 \(O(n \div k)\)。\(k\) 是一个不定值，取值范围为 \(1 \sim n\)。

显然，当 \(n\) 比较大的时候两种暴力做法都不可取，但是可以考虑把它们结合起来——具体地，取 \(k = \sqrt{n}\)，那么两种方法的时间复杂度就都是 \(O(\sqrt{n})\) 级别的了。

分割开来。如果给定的 \(k\) 值 \(\le \sqrt{n}\)，就采取暴力方案一，反之，采取暴力方案二。

这，就是根号分治。

解答根号分治题目的方案

解决根号分治的题目很简单。联想到根号分治更是简单。

为什么这么说呢？因为根号分治的本质就是把两种暴力算法拼凑在一起而已，因此只要想题的时候想到了两种不同的暴力算法并且可以拼起来就行啦。注意时间复杂度的一个取向不能是完全相同的，不然就没雨意义了。

例题一：CF797E

上来就可以想到两种最暴力的方案：

直接上 DP，算出每种 \(p\) 和 \(k\) 的答案。
- 具体地，定义 \(dp_{i,j}\) 表示 \(p=i\) 且 \(k=j\) 的情况下，需要执行多少次操作。
- 转移的时候倒序枚举 \(i\) 从 \(n\) 到 \(1\)，正序枚举 \(j\) 从 \(1\) 到 \(n\)。
- 然后判断一下，如果 \(i+a_i+j>n\) 那么直接让 \(dp_{i,j} = 1\)，否则转移 \(dp_{i,j} = dp_{i+a_i+j,j} + 1\)。
询问给定 \(p\) 和 \(k\) 之后直接暴力模拟。
- 这个显然不用怎么多说，一直 while 循环按照题目所述来模拟一遍。
- 每次让 \(p \gets p+a_p+k\)，然后 \(cnt \gets cnt+1\)，直到 \(p > n\) 就跳出。
- 输出 \(cnt\) 所得数值即可。

显然这两种方案直接做都是会超时的，但是想想看吧，当 \(k\) 比较小的时候完全是可以一开始做一遍 DP 预处理出答案的，这样子时间复杂度并不会超；而当 \(k\) 很大的时候，暴力模拟的次数也会大大降低，因此时间复杂度也可以接受了。

考虑取分界线为 \(\sqrt{n}\)，~~毕竟它叫根号分治，怎么也要在根号的位置分一下界吧，哈哈~~。

具体地，DP 只做到 \(dp_{n,\sqrt{n}}\)，即只取到 \(k \le \sqrt{n}\)，那么最开始预处理的 \(O(n \sqrt{n})\) 的时间复杂度就可以接受了，那么查询的时候一旦 \(k \le \sqrt{n}\) 就直接输出 DP 具体值就 OK 了；而后面的暴力做法则只在查询的时候，给定 \(k > \sqrt{n}\) 的时候使用，毕竟不管 \(p\) 的原始值和中间的所有 \(a_p\) 再小，就是加上个 \(\sqrt{n}\) 次 \(k\) 都会直接超出 \(n\) 的范围，这样下来时间复杂度也是 \(O(q \sqrt{n})\) 的，完全没有问题！

然后就结束了。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5 , M = 405;
int n,m,Q,a[N],dp[N][M];
int read(){int su=0,pp=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}return su*pp;
}
int main(){n=read();m=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=n;i>=1;i--)for(int j=1;j<=m;j++)dp[i][j]=(i+a[i]+j>n?1:dp[i+a[i]+j][j]+1);Q=read();while(Q--){int p=read(),k=read();if(k<=m)cout<<dp[p][k]<<"\n";else{int cnt=0;while(p<=n)p+=a[p]+k,cnt++;cout<<cnt<<"\n";}}return 0;
}

见证到根号分治的力量了吗？它可以轻松将两种暴力结合起来，成为正解！

例题二：CF786C

仍然考虑两种暴力方案：

直接暴力算出每个 \(k\) 所对应的划分的方案。
- 具体地，可以使用类似双指针的方法，把整个数列扫一遍。
- 由于 \(k\) 已经固定，因此限制是已经知道了的。
- 可以用桶标记目前出现过的数字，每次新加一个数就将桶的那个位置置为 \(1\)，并且根据这次是否是第一次出现来加减 \(cnt\)。
- 如果 \(cnt\) 超过 \(k\) 了，那么就要 \(ans \gets ans + 1\)，并且重置桶和 \(cnt\)，然后不断计算就行了。
- 注意出了循环之后如果还有遗留的 \(cnt\)，也要 \(ans \gets ans + 1\) 哦。
- 当然，不要忘记最后还得清空桶哦！
用二分的方式，每次求出某个 \(k\) 的答案后，就二分到这种答案能延续到哪个 \(k^\prime\) 的位置，然后把所有 \(k \sim k^\prime\) 的 \(ans\) 值全部重置。
- 显然是二分答案，但是 check 函数是非常简单的。
- 因为其逻辑就和第一种暴力方案是一样的，只不过最后返回的并不是 \(ans\)，而是 \(ans\) 是否在要求的区间划分个数内。
- 但是显然不能一个个枚举 \(k\) 啊，所以记录上一次到达的位置（即之前的 \(k^\prime\)），然后每次新开一轮就是 \(k = k^\prime_{last} + 1\) 了。
- 实质上应该枚举的不是 \(k\)，而是填进答案里的数值，即要求的区间划分个数 \(m\)。
- 每次算出新的 \(k\) 之后都得先 check 一下这个 \(m\) 是否正确，如果不对的话说明最后的 \(ans\) 中没有一个答案为 \(m\) 的，那么直接跳过这一轮循环就好了。

但是显然上面两种方案单独拎出来做都是不现实的。但是可以考虑根号分治结合它们呀！

分界线为 \(\sqrt{n}\)。

首先用第一种暴力方案算出 \(1 \sim \sqrt{n}\) 的所有 \(k\) 的答案，然后从 \(ans_k\) 开始枚举 \(m\)，用第二种暴力方案挨个算就好了。

看看时间。第一种暴力方案的时间复杂度是 \(O(n \sqrt{n})\)，嗯，过关了；第二种暴力方案的时间复杂度则是 \(O(n \sqrt{n} \log n)\)，虽然比第一种多个 \(\log\)（毕竟要二分嘛），但是也能过。

所以就 A 啦！

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define pii pair<int,int>
#define fr first
#define se second
#define pb push_back
using namespace std;
const int N = 1e5+5;
int n,Sq,a[N],Ans[N],Last;bool vis[N];
int min(int x,int y){return (x<y?x:y);}
int max(int x,int y){return (x>y?x:y);}
int read(){int su=0,pp=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}return su*pp;
}
bool check(int m,int k){int cnt=0,lst=1,sum=0;for(int i=1;i<=n;i++){if(!vis[a[i]])vis[a[i]]=1,cnt++;if(cnt<=k)continue;for(int j=lst;j<=i;j++)vis[a[j]]=0;cnt=1,vis[a[i]]=1,sum++,lst=i;}if(cnt){for(int j=lst;j<=n;j++)vis[a[j]]=0;sum++;}return (sum<m);
}
int main(){n=read(),Sq=sqrt(n)+1,Last=Sq+1;for(int i=1;i<=n;i++)a[i]=read();for(int k=1;k<=Sq;k++){int cnt=0,lst=1;for(int i=1;i<=n;i++){if(!vis[a[i]])vis[a[i]]=1,cnt++;if(cnt<=k)continue;for(int j=lst;j<=i;j++)vis[a[j]]=0;cnt=1,vis[a[i]]=1,Ans[k]++,lst=i;}if(cnt){for(int j=lst;j<=n;j++)vis[a[j]]=0;Ans[k]++;}}for(int m=Sq;m>=1;m--){int l=Last,r=n+1,Ed=Last;if(check(m,l))continue;while(l<=r){int mid=(l+r)>>1;if(check(m,mid))Ed=mid,r=mid-1;else l=mid+1;}for(int i=Last;i<Ed;i++)Ans[i]=m;Last=Ed;}for(int i=Last;i<=n;i++)Ans[i]=1;for(int i=1;i<=n;i++)cout<<Ans[i]<<" ";cout<<"\n";return 0;
}