目录
- 根号分治
- 待补
正文
根号分治
其实分块也是一种根号分治。
本质是将一组询问按照某个值域来划分（通常取根号），不超过 \(X\) 时采用一种做法，超过了换另一种（一般一种是暴力，另外一个空间换时间或采用其他一些的算法结合）。
例：洛谷 P3396
首先显然有一个 for(int i=y;i<=n;i+=x) 的暴力。这个暴力的运行时间取决于 \(x\) 的大小。所以注意到当 \(x\) 大于或等于 \(\sqrt{n}\) 的时候可以实现 \(O(n\sqrt{n})\) 的优秀复杂度。
小于的话预处理一下空间换时间即可。
当然目前为止没有修改。
修改只要把预处理的那一部分把与修改的地方相关的（约 \(\sqrt{n}\) 个）改掉，其他部分依托依靠暴力就可以了。
然后这个题就被秒掉了。
查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans[1005][1005],n,m,a[150005],base;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
base=sqrt(n)+1;
for(int i=1;i<=n;++i){
cin>>a[i];
for(int j=1;j<=base;++j)ans[j][i%j]+=a[i];
}
for(int i=1;i<=m;++i){
char c;
int x,y;
cin>>c>>x>>y;
if(c=='A'){
if(x<=base){
cout<<ans[x][y]<<'\n';
}
else{
int sum=0;
for(int j=y;j<=n;j+=x)sum+=a[j];
cout<<sum<<'\n';
}
}
else{
for(int j=1;j<=base;++j)ans[j][x%j]-=a[x];
a[x]=y;
for(int j=1;j<=base;++j)ans[j][x%j]+=a[x];
}
}
return 0;
}