根号分治 - qnxy

简介

对于一类问题，有两种或多种不同的解法，均无法单独在时限内过题，但在特定的数据范围内优势明显。这时可以设定阈值，对于不同的数据范围，使用不同的算法，令总时间复杂度可以接受。

常见的阈值： $\sqrt{n}$ 等。

例题

CF797E

根号分治入门题，有两种解法：

用时间换空间：对于每一次询问，暴力模拟出结果，复杂度 $O(nk)$ 。

用空间换时间：DP 预处理出每一个位置，对于每个会出现的 $k$ 的答案。预处理 $O(nk)$ ，查询 $O(1)$ 。

显然当 $k > \sqrt{n}$ 时， $p$ 移动的次数不超过 $\sqrt{n}$ ，当 $k < \sqrt{n}$ 时， $O(n\sqrt{n})$ 的空间和时间复杂度可以接受。

简单的说，方法一 $k$ 越大越好，方法二 $k$ 越小越好。

所以以 $\sqrt{n}$ 为阈值，分别使用两种方法，总时间复杂度为 $O(n\sqrt{n})$ 。

#include <bits/stdc++.h>
#define rei register int
#define N 110010
using namespace std;

template <typename T> inline void read(T &x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int n, m, f[N][351], num, que[N], ed, a[N], ans[N], xx[N], yy[N];

inline void Pre()
{
	for (rei i = n; i >= 1; i--)
	{
		for (rei j = 1; j <= ed; j++)
		{
			if (i + a[i] + que[j] > n) f[i][que[j]] = 1;
			else f[i][que[j]] = f[i + a[i] + que[j]][que[j]] + 1;
		}
	}
}

int main()
{
	read(n); num = sqrt(n);
	for (rei i = 1; i <= n; i++) read(a[i]); 
	read(m); 
	for (rei i = 1; i <= m; i++)
	{
		int x, y; read(x); read(y); xx[i] = x; yy[i] = y;
		if (y <= num) que[++ed] = y;
		else
		{
			int cnt = 0;
			while (x <= n) x = x + a[x] + y, cnt++;
			ans[i] = cnt;
		}
	} 
	sort(que + 1, que + 1 + ed); ed = unique(que + 1, que + 1 + ed) - que - 1; Pre();
	for (rei i = 1; i <= m; i++)
	{
		if (ans[i]) printf("%d\n", ans[i]);
		else printf("%d\n", f[xx[i]][yy[i]]);
	}
	return 0;
}

CF103D

跟上一道题几乎一样，但这道题求的是总和。

但如果你直接交上一发，就会发现 MLE。

因为出题人~~那个聪明仔~~只开了 70M 空间。

其实仔细思考，发现上一题故意少讲了个空间优化。

由于询问离线，可以对于每个询问按 $k$ 从小到大排序。

当 $k<\sqrt{n}$ 时，问到哪个 $k$ ，就对它进行预处理，这样就省去了 dp 数组保存 $k$ 的一维，空间复杂度从 $O(n\sqrt{n})$ 变为 $O(n)$ 。

$k > \sqrt{n}$ 时仍然暴力跳。

#include <bits/stdc++.h>
#define rei register int
#define N 300010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

ll n, a[N], m, T, ans[N], ed, X[N], Y[N], f[N];
struct Node {ll x, y, id;} q[N];

inline bool cmp(const Node &a, const Node &b) {return a.y < b.y;}

int main()
{
	read(n); T = sqrt(n);
	for (rei i = 1; i <= n; i++) read(a[i]);
	read(m);
	for (rei i = 1; i <= m; i++) read(q[i].x), read(q[i].y), q[i].id = i;
	sort(q + 1, q + 1 + m, cmp);
	for (rei i = 1; i <= m; i++)
	{
		if (q[i].y >= T) {for (rei j = q[i].x; j <= n; j += q[i].y) ans[q[i].id] += a[j]; continue;}
		if (q[i].y != q[i - 1].y) for (rei j = n; j; j--) f[j] = a[j] + f[j + q[i].y];
		ans[q[i].id] = f[q[i].x];
	}
	for (rei i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	return 0;
}

P3396 哈希冲突

一道背景出得不错的题，看出本质脑子要转个弯。

首先不要看错题，取模的是下标。~~否则我就不会做了~~

对 $p$ 取模相同的数在同一个池，假如你像笔者一样蠢的话，你就要看上好一会儿才醒悟：

在同一个池的数，间隔为 $p$ 。

那这道题就又跟上面两道例题重合了。~~好的我不讲了，做法显然~~

建议不往下看，自己先做试下。

~~因为笔者 10min 就一发 A 掉了，要不是手速太慢还可以更快。~~

大框架是一样的，但是这题带修，所以就不能像上一题一样压缩空间了。但是 dp 数组的两维也分别只有 $\sqrt{n}$ ，总空间为 $O(n)$ ，完全够用。（此处感谢 @꧁阿离꧂ 勘误）

修改时，将包含 $value_x$ 的池减去旧值，加上新值。

#include <bits/stdc++.h>
#define rei register int
#define N 150010
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

ll n, m, f[405][405], T, ans[N], a[N];

int main()
{
	read(n); read(m); T = sqrt(n);
	for (rei i = 1; i <= n; i++) read(a[i]);
	for (rei i = n; i; i--)
		for (rei j = 1; j <= T; j++)
			f[j][i % j] += a[i];
	for (rei i = 1; i <= m; i++)
	{
		char opt; ll x, y; cin >> opt; read(x); read(y);
		if (opt == 'A')
		{
			if (x >= T) for (; y <= n; y += x) ans[i] += a[y];
			else ans[i] = f[x][y];
		}
		else if (opt == 'C')
		{
			ans[i] = -1;
			for (rei j = 1; j <= T; j++) f[j][x % j] = f[j][x % j] - a[x] + y;
			a[x] = y;
		}
	}
	for (rei i = 1; i <= m; i++) if (ans[i] != -1) printf("%lld\n", ans[i]);
	return 0; 
}

CF1039D

图论+根号分治

考虑暴力，类似[NOIP2018]赛道修建，对于每一个不同的 $k$ ，从叶节点开始向上遍历，贪心地取。尽量在子树内取够 $k$ ，否则该简单路径向父亲方向延展。复杂度 $O(nk)$ 。

定义 $T$ 为阈值，发现 $k < T$ 时，简单路径的数量（即答案）不大于 $\dfrac{n}{T}$ 。当 $k$ 大到某个程度时，可能的不同的答案值数量远小于 $k$ 。

也就是说，多个 $k$ 的答案都是相同的。

同时有个显然的结论，随着 $k$ 增大，答案必定单调递减（非严格）。

所以拥有相同答案的 $k$ ，它们一定是连续的。

因此只要根据单调性，二分求出最后一个答案相同的 $k$ ，那么中间的这些 $k$ 的答案只用求一次即可。具体操作参考代码。由于只有 $\dfrac{n}{T}$ 种答案，所以也只用二分 $\dfrac{n}{T}$ 次， $\text{check}$ 过程是 $O(n)$ 的，复杂度为 $O(\dfrac{n^2 \log n}{T})$

时间复杂度 $O(nT+\dfrac{n^2 \log n}{T})$

用基本不等式发现当 $T=\sqrt{n\log n}$ 时最优，复杂度为 $O(n\sqrt{n\log n})$

#include <bits/stdc++.h>
#define rei register int
#define N 200010
using namespace std;

template <typename T> inline void read(T &x)
{
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -f; ch = getchar();}
	while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
	x *= f;
}

int n, head[N], edge_cnt = 1, ans[N], f[N], fa[N], dfn[N], dfs_cnt, T;
struct edge {int nxt, v;} e[N << 1];

inline void add_edge(int u, int v) {e[++edge_cnt].nxt = head[u]; head[u] = edge_cnt; e[edge_cnt].v =v;}

inline void Dfs(int u, int pre)
{
	fa[u] = pre;
	for (rei i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].v;
		if (v == pre) continue;
		Dfs(v, u);
	}
	dfn[++dfs_cnt] = u;
}

inline int solve(int k)
{
	int ret = 0;
	for (rei i = 1; i <= n; i++) f[i] = 1;
	for (rei id = 1; id <= n; id++)
	{
		int u = dfn[id];
		if (!fa[u] || f[u] == -1 || f[fa[u]] == -1) continue;
		if (f[fa[u]] + f[u] >= k) f[u] = f[fa[u]] = -1, ret++; // 连子树 
		else f[fa[u]] = max(f[u] + 1, f[fa[u]]); // 向上连 
	}
	return ret;
}

int main()
{
	read(n); T = sqrt(n * log2(n));
	for (rei i = 1; i < n; i++)
	{
		int u, v; read(u); read(v);
		add_edge(u, v); add_edge(v, u);
	} 
	Dfs(1, 0); ans[1] = n; 
	for (rei i = 2; i <= T; i++) ans[i] = solve(i);
	for (rei i = T + 1; i <= n; i++)
	{
		int le = i, ri = n, mid, tmp = solve(i), ret;
		while (le <= ri)
		{
			mid = (le + ri) >> 1;
			if (solve(mid) == tmp) le = mid + 1, ret = mid;
			else ri = mid - 1;
		}
		for (rei j = i; j <= ret; j++) ans[j] = tmp;
		i = ret;
	}
	for (rei i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}