根号分治及例题

根号分治的思想简介

根号分治，实际上是一种基于阈值的数据点分治。在询问小于等于和大于时分别有两种算法。这两种算法在它们的数据范围内都适用，不会超时。一般我们设置为带根号的一个值，来维护时间复杂度平衡。

这里先讲一道板题：

CF1207F Remainder Problem IN Lv.13

这道题首先考虑暴力：

一种暴力是，加上就直接加，查询的时候就直接枚举所有下标的位置，这种方法的修改复杂度为，查询时间复杂度为。
另一种暴力是，枚举模数，开一个二维数组，表示所有的下标的位置的值之和。修改的时候就枚举所有的，就可以得到现在修改的下标的结果，然后修改。查询直接查即可。修改时间复杂度为，查询时间复杂度为。

现在我们得到了这两种暴力。而根号分治的用处这时就体现出来了。很明显，现在要糅合这两种暴力，因为第一种暴力的时间复杂度随的增大而减小，所以适合在模数值较大时使用。而另一种暴力复杂度随的增大而增大，所以适合在模数值较小时使用。

我们就定一个阈值，在时使用第二种暴力，在时使用第一种暴力。为了让两种时间复杂度平衡，就算两种暴力的平均复杂度，在时取等。所以设置阈值为。

也就是，记录所有的模数的值，修改操作就枚举所有的，然后复杂度修改。

然后在查询操作 2 x y 的时候，若，那么直接查值。否则暴力枚举的，时间复杂度最多也就是，放心大胆枚。

于是，这道题的时间复杂度就被平衡为了。

#include<bits/stdc++.h>
using namespace std;
const int N = 5000009;
const int L = 707; //sqrt(5e6)
int a[N];
int sum[L+1][L+1];
int n=500000, q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>q;
    int op, x, y;
    while(q--){
        cin>>op>>x>>y;
        if(op == 1){
            a[x] += y;
            for(int mod=1;mod<=L;mod++){
                sum[mod][x%mod] += y;
            }
        }else{
            if(x <= L){
                cout<<sum[x][y]<<'\n';
            }else{
                int ans = 0;
                for(int i=y;i<=n;i+=x) ans += a[i];
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}

HDU4858 项目管理

这道题似乎是我做的第一道 HDU。这道题很经典。

有两种暴力做法：

第一种，是直接暴力模拟，修改，查询。
第二种，是记录所有点的相邻项目的能量值的和，修改，查询。

于是开始平衡一下复杂度：我们定一个阈值。设所有的点都为“轻点”，的点都称为“重点”。

那么我们就记录，每一个点的所有的相邻“重点”编号（不会超过个）。和所有重点的相邻项目的能量值的和。然后修改就修改这个点权值，并且也要修改与这个点相邻的所有重点的值。

查询的时候，如果，那么直接暴力查询，时间复杂度。否则就直接输出值，时间复杂度。

所以把设为时，可以平衡时间复杂度。最终复杂度。

CF710D Two Arithmetic Progressions IN Lv.15

CF 2500。正解要使用 EX-GCD 状物。但是这里是根号分治区，所以我们要使用根号分治来艹过去。

首先，容易发现一个性质，假设某个数在两个等差数列都出现过，那么下一个在等差数列出现的数就一定是。因为对于两个等差数列，一个循环的周期就是。中间不会再有在两个等差数列中出现的数字，否则就不符合函数的性质。

所以我们可以看什么变量可以分出一个“阈值”出来。

一个暴力解法是，钦定，然后枚举所有的在并且在公差为的等差数列里面的数字，看它在不在公差为的等差数列里面即可。时间复杂度。
另一种暴力解法是，因为一个周期，所以我们只要找到里面第一个在两个等差数列里的数就可以了。

那就可以首先把设置为第二个等差数列里第一个比和都大的值。这是等价的，肯定要在和范围之内。然后搜索里面有没有同时在两个等差数列里面存在的数。
- 若没有，则答案为。
- 若有，则记录这个数的值。根据循环周期和可以算出来还有多少个重复的，也就是还有多少个周期在里面。
时间复杂度。

我们发现，时间复杂度还是典型的和两种。所以可以断定结论：设置。如果，那么使用第二种暴力解法，否则使用第一种。时间复杂度被平衡到。

其他例题

P8250 交友问题 IN Lv.14

还是两种暴力方法：

记录所有点的相邻的点。然后搜索的时候就遍历的邻点，看有没有这条边。若没有，就算答案。否则不算。预处理时间复杂度，时间复杂度。
将所有点的邻边都以 bitset 形式存每一个点里。相当于是一个第二维为 bitset 的邻接矩阵 bitset<N> nxt[N]。然后查询的时候就查 nxt[u] & (nxt[u] ^ nxt[v]) 的 popcount 即可。nxt[u]^nxt[v] 代表和都没有连边的点集。最后 and 一下的点集即可。预处理时间复杂度，查询时间复杂度。

于是我们还是，设定一个阈值。然后的使用第一种方法，否则使用第二种（容易发现第二种点不超过个）。为了节省空间，bitset 的邻接矩阵的第一维就使用 vector 存储。

于是第一种的暴力的时间复杂度就变为了，第二种暴力的时间复杂度就变为了。为了使时间、空间都正确，这里设置即可。

P9809 [SHOI2006] 作业 IN Lv.13

还是，两种暴力：

直接模拟。修改复杂度，查询复杂度。虽然也是一种暴力，但是没有优化空间。重新想。
枚举，记录所有数的的最小值。查询时直接查即可。修改复杂度，查询复杂度。
对第一种暴力进行一种优化：记录集合（就是原题的集合），枚举的倍数（从开始枚举直到），记其为。那么目前答案就是中大于等于的第一个数减去，即 *S.lower_bound(now) - now。修改复杂度，查询复杂度。

现在对第二种和第三种设定一个阈值，当时，使用第二种暴力，否则使用第三种。那么设定其为，总的时间复杂度就是。