行业知识
根号分治(根号算法)
���根号算法,然而不是分块;
()是论文,然而不是莫队;
是暴力美学,然而不是暴力。
()例题
- 哈希冲突
- R e m a i n d e r P r o b l e m Remainder Problem RemainderProblem
这两题貌似没有区别,我们以 R e m a i n d e r P r o b l e m Remainder Problem RemainderProblem 作为例子来介绍。
题目描述
给你一个长度为 500000 500000 500000 的序列,初值为 0 0 0 ,你要完成 q q q 次操作,操作有如下两种:
- 1 x y : 将下标为 x x x 的位置的值加上 y y y
- 2 x y : 询问所有下标模 x x x 的结果为 y y y 的位置的值之和
思路
这道题要我们求的,就是以下程序:
for(int i=y;i n x > \sqrt{n} x>n 时,就暴力求解; x ≤ n x \le \sqrt{n} x≤n 时,则预处理出答案。如此,当数据 ≤ n \le \sqrt{n} ≤n 时,每次修改的时间复杂度为为 O ( n ) O(\sqrt{n}) O(n ) ,查询的为 O ( 1 ) O(1) O(1) ;
当数据 > n > \sqrt{n} >n 时,每次修改的时间复杂度为 O ( 1 ) O(1) O(1) ,查询的为 O ( n ) O(\sqrt{n}) O(n ) 。
通过根号分治,我们就能实现两种操作的时间复杂度均分 。
对于预处理,我们用 f i , j f_{i,j} fi,j 表示所有下标模 i i i 为 j j j 的数的和。
f f f 数组只需开到 n ∗ n \sqrt{n} * \sqrt{n} n ∗n ,所以空间也不会爆。
代码
#includeusing namespace std;const int maxn=5e5+5,N=5e5,sqrtn=710;int q;long long a[maxn],f[sqrtn][sqrtn];int main(){cin>>q;int opt,x,y,tmp=sqrt(N);while(q--){scanf("%d%d%d",&opt,&x,&y);if(opt==1){ //修改操作 for(int i=1;i //查询操作 if(xlong long ans=0;for(int i=y;i