根号分治 学习笔记

个人感觉这个思想还是蛮神奇的（？ 膜拜发明人/bx --- [来看题](https://www.luogu.com.cn/problem/P3396) 先考虑暴力。对于每个询问，执行以下代码： ```cpp 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$ 时，执行以下代码： ```cpp 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)$。 ```cpp #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很有用。~~ --- [再来看这个](https://www.luogu.com.cn/problem/CF1039D) 先考虑暴力贪心。对于每个$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$，然后用数组模拟求解。 ```cpp #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; } ``` --- 几道习题： - [LOJ #2838. 「JOISC 2018 Day 3」比太郎的聚会](https://loj.ac/p/2838) - [P5397 [Ynoi2018] 天降之物](https://www.luogu.com.cn/problem/P5397)（相信我，这题完全可做）