ConanKIDの小窝

ConanKIDの小窝

根号分治 学习笔记

posted on 2021-10-04 15:32:01 | under 学习笔记 |

个人感觉这个思想还是蛮神奇的(?

膜拜发明人/bx


来看题

先考虑暴力。对于每个询问,执行以下代码:

for (int i = y; i <= n; i += x)
    ans += a[i];

但是这段代码的复杂度是 $O(\frac{n}{x})$ 的,最坏情况将会达到 $O(n)$,无法承受。

分析一下,发现当 $x$ 比较大时,时间复杂度是可以保证的。

再来考虑另一种暴力。我们预处理出一个数组 $cnt$,$cnt_{x,y}$ 表示序列中模 $x$ 余 $y$ 的所有位置上的数的和。把 $a_x$ 修改为 $y$ 时,执行以下代码:

for (int j = 1; j <= n; j++)
    cnt[j][x % j] -= (a[x] - y);
a[x] = y;

这样询问的复杂度是 $O(1)$,修改复杂度是 $O(n)$。

这个算法当所有 $x$ 都比较小时,复杂度是正确的,可以做到 $O(x)$。

于是,我们是否可以把上述两种暴力组合起来——当 $x$ 较大时,执行暴力一;当 $x$ 较小时,执行暴力二。

具体来说,我们设置一个阀值 $lim$,当询问的 $x\le lim$时,直接输出我们维护的 $cnt$;反之,暴力循环统计。修改时正确维护 $cnt$ 即可。

时间复杂度为 $O(n(lim+\frac{n}{lim}))$。由均值不等式可知,取 $lim=\sqrt{n}$ 时,理论复杂度最优,为 $O(n\sqrt{n})$。空间复杂度为 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 150005, maxb = sqrt(150000) + 5;
int n, m, block;
int a[150005];
int cnt[maxb][maxb];
int main() {
    cin >> n >> m; block = sqrt(n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= block; i++)
        for (int j = 1; j <= n; j++)
            cnt[i][j % i] += a[j];//预处理出cnt
    for (int i = 1; i <= m; i++) {
        char p; int x, y; cin >> p >> x >> y;
        if (p == 'A') {
            if (x <= block) cout << cnt[x][y] << endl;
            else {
                int ans = 0;
                for (int j = y; j <= n; j += x)
                    ans += a[j];
                cout << ans << endl;
            }//分情况采用不同方法统计答案
        } else {
            for (int j = 1; j <= block; j++)
                cnt[j][x % j] -= (a[x] - y);
            a[x] = y;//维护cnt
        }
    }
    return 0;
}

我们发现,修改复杂度为 $O(lim)$,询问复杂度有时为 $O(lim)$,有时为 $O(\frac{n}{lim})$。因此可以考虑适当调小 $lim$ 使实际效率更高。经过测试,当 $lim$ 取 $n^{\frac{1}{3}}$ 时,实际表现最佳。

卡常技巧一定要学好,做Ynoi很有用。


再来看这个

先考虑暴力贪心。对于每个$k$,直接dfs整棵树,能拼成一条长度为$k$的路径就拼。正确性显然。时间复杂度$O(n^2)$。

考虑根号分治。设$ans_i$表示$i$合法路径集的答案。设置阈值$lim$,对于$k\le lim$,暴力单独求解。

接下来处理大于$lim$的$k$。显然,$x$合法路径的集合大小不超过$\frac{n}{x}$,因此$ans_{lim+1},ans_{lim+2},\cdots,ans_n$显然至多只有$\frac{n}{lim}$种取值。我们又发现$ans$是单调不增的,因此可以考虑以下流程:

  1. 设置指针$i$,首先指向$lim+1$;
  2. dfs求出$ans_i$,同时在$i$的右边二分,找出最后一个与$i$答案相同的点,并把这一段的答案都更新为$ans_i$;
  3. 重复以上过程,直至求解完毕。

分析一波复杂度。对于前一部分的求解,时间复杂度为$O(n\times lim)$;对于后一部分,我们最多二分$\frac{n}{lim}$次,每次二分的复杂度为$O(n\log n)$,因此总的复杂度为$O(n\times lim+\frac{n^2\log n}{lim})$。当$lim$取$\sqrt{n\log n}$时,理论复杂度最优,为$O(n\sqrt{n\log n})$。

需要注意,这道题有点卡常,求解不能直接dfs,需要预处理出$dfn$,然后用数组模拟求解。

#include<bits/stdc++.h>
using namespace std;
int n, block;
vector<int> a[100005];
int dfn[100005], cnt;
int f[100005], s[100005];
int ans[100005];
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
    return x * f;
}
void dfs(int fa, int x) {
    for (int i = 0; i < a[x].size(); i++) {
        int y = a[x][i];
        if (y == fa) continue;
        f[y] = x; dfs(x, y);
    }
    dfn[++cnt] = x;
}//预处理
int check(int k) {//求出ans[k]
    int ans = 0;
    for (int i = 1; i <= n; i++)
        s[i] = 1;
    for (int i = 1; i <= n; i++) {
        int u = dfn[i];
        if (f[u] && s[u] != -1 && s[f[u]] != -1)
            if (s[f[u]] + s[u] >= k) ans++, s[f[u]] = -1;//能拼就拼
            else s[f[u]] = max(s[f[u]], s[u] + 1);
    }
    return ans;
}
int main() {
    n = read(); block = sqrt(n * log2(n));
    for (int i = 1; i < n; i++) {
        int x = read(), y = read();
        a[x].push_back(y); a[y].push_back(x);
    }
    dfs(0, 1);
    printf("%d\n", n);
    for (int i = 2; i <= block; i++)
        printf("%d\n", check(i));
    for (int i = block + 1; i <= n; i++) {
        int x = check(i), l = i, r = n + 1;
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (check(mid) == x) l = mid;
            else r = mid;
        }//二分
        for (; i <= l; i++) printf("%d\n", x);
        i--;
    }
    return 0;
}

几道习题: