根号分治

根号分治是一种优美的暴力。

顾名思义，根号分治就是对于一个长度为$N$的数列，将查询和修改分为$\le N$和$>N$的两个部分来处理。将两个部分分别处理并拼在一起，来优化时间复杂度。

例题

洛谷P3396 哈希冲突

有一个长度为$n$的序列$a$和$m$次操作，每次操作有两个类型：

• 查询所有满足$k\%x=y$的$a_k$之和
• 将$a_x$修改为$y$

$1\le n\le 150000,1\le m\le 150000,1\le a_i\le 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(nm)$的，我们考虑优化。

我们发现，如果当前是第一种操作且$x>\sqrt{n}$时，一次查询是$O(\sqrt{n})$的。然而，在$x\le \sqrt{n}$时，时间复杂度就变大了。我们考虑对$x\le \sqrt{n}$的部分特殊处理一下。

设$f_{i,j}$表示模数为$i$时所有下标模$i$为$j$的数之和，那么我们用$O(n\sqrt{n})$处理出$1\le i\le sqrtn$且$0\le j<i$的所有$f_{i,j}$之和。

那么，在查询时，若$x\le \sqrt{n}$，直接在$f_{i,j}$上$O(1)$查询；若$x>n$，则$O(\sqrt{n})$暴力查询。在修改时，我们$O(\sqrt{n})$修改$f_{i,j}$，再$O(1)$修改$a_i$，那么时间复杂度就降为$O((n+m)\sqrt{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;
}