本文主要是介绍浅谈根号分治,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
根号分治
根号分治是一种优美的暴力。
顾名思义,根号分治就是对于一个长度为 N N N的数列,将查询和修改分为 ≤ N \leq N ≤N和 > N >N >N的两个部分来处理。将两个部分分别处理并拼在一起,来优化时间复杂度。
例题
洛谷P3396 哈希冲突
有一个长度为 n n n的序列 a a a和 m m m次操作,每次操作有两个类型:
- 查询所有满足 k % x = y k\% x=y k%x=y的 a k a_k ak之和
- 将 a x a_x ax修改为 y y y
1 ≤ n ≤ 150000 , 1 ≤ m ≤ 150000 , 1 ≤ a i ≤ 1000 1\leq n\leq 150000,1\leq m\leq 150000,1\leq a_i\leq 1000 1≤n≤150000,1≤m≤150000,1≤ai≤1000
解题思路
首先,我们考虑暴力。
code
#include<bits/stdc++.h>
using namespace std;
int n,m,B,x,y,ans,a[150005];
char ch;
int main()
{scanf("%d%d",&n,&m);B=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}while(m--){ch=getchar();while(ch!='A'&&ch!='C') ch=getchar();scanf("%d%d",&x,&y);if(ch=='A'){ans=0;for(int i=y;i<=n;i+=x) ans+=a[i];printf("%d\n",ans);}else a[x]=y;}return 0;
}
这个暴力是 O ( n m ) O(nm) O(nm)的,我们考虑优化。
我们发现,如果当前是第一种操作且 x > n x>\sqrt n x>n时,一次查询是 O ( n ) O(\sqrt n) O(n)的。然而,在 x ≤ n x\leq \sqrt n x≤n时,时间复杂度就变大了。我们考虑对 x ≤ n x\leq \sqrt n x≤n的部分特殊处理一下。
设 f i , j f_{i,j} fi,j表示模数为 i i i时所有下标模 i i i为 j j j的数之和,那么我们用 O ( n n ) O(n\sqrt n) O(nn)处理出 1 ≤ i ≤ s q r t n 1\leq i\leq sqrt n 1≤i≤sqrtn且 0 ≤ j < i 0\leq j<i 0≤j<i的所有 f i , j f_{i,j} fi,j之和。
那么,在查询时,若 x ≤ n x\leq \sqrt n x≤n,直接在 f i , j f_{i,j} fi,j上 O ( 1 ) O(1) O(1)查询;若 x > n x>n x>n,则 O ( n ) O(\sqrt n) O(n)暴力查询。在修改时,我们 O ( n ) O(\sqrt n) O(n)修改 f i , j f_{i,j} fi,j,再 O ( 1 ) O(1) O(1)修改 a i a_i ai,那么时间复杂度就降为 O ( ( n + m ) n ) O((n+m)\sqrt n) O((n+m)n)。
code
#include<bits/stdc++.h>
using namespace std;
int n,m,B,x,y,ans,a[150005],f[405][405];
char ch;
int main()
{scanf("%d%d",&n,&m);B=sqrt(n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=B;i++){for(int j=1;j<=n;j++) f[i][j%i]+=a[j];}while(m--){ch=getchar();while(ch!='A'&&ch!='C') ch=getchar();scanf("%d%d",&x,&y);if(ch=='A'){if(x<=B) printf("%d\n",f[x][y]);else{ans=0;for(int i=y;i<=n;i+=x) ans+=a[i];printf("%d\n",ans);}}else{for(int i=1;i<=B;i++) f[i][x%i]+=y-a[x];a[x]=y;}}return 0;
}
这篇关于浅谈根号分治的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!