根号算法

名言：根号算法不只是分块

包括但不限于：各种类型的分块以及根号分治

分块

优雅的暴力，做的不算很多，一般来讲初始化如下：

sq=sqrt(n);
for (int i=1;i<=sq;i++) st[i]=n/sq*(i-1)+1,ed[i]=n/sq*i;
if(ed[sq]!=n) st[sq+1]=ed[sq]+1,ed[sq+1]=n,sq++;

常见操作：

• 记录一个$mark$数组，记录整块的区间变动信息

• 对于散块暴力查，对于整块直接累计答案贡献

• 维护整块元素出现次数可以固定一个块的起点，然后直接向后扫完所有块，$O(n\sqrt{n})$统计

根号分治

标志：循环出现+=x，且x是和n一个数量级，执行$n$次？

发现我们对于小于$\sqrt{n}$的部分预处理是$O(n\sqrt{n})$的，对于大于暴力总的复杂度为$qO(n/x)$，因为$x>\sqrt{n}$，所以询问部分是$qO(\sqrt{n})$的，总的就做到了$O((n+q)\sqrt{n})$

例题：P3396 哈希冲突