自动搬运

查看原文

来自洛谷，原作者为

	Renshey 滚落沙尘，泛生浮光。掠影千年，奔走四方。

搬运于2025-08-24 22:45:02，当前版本为作者最后更新于2023-02-11 12:41:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑套用平面最近点对的网格化做法。在平面最近点对中，每次选取当前答案 $d$ 作为边长，将平面划分为每一格大小为 $d \times d$ 的网格，然后每个网格中只会有 $O(1)$ 个点，只需要枚举相邻（至少有一个公共点）的两个网格计算贡献即可。

考虑拓展上述做法，实际上只需要关心 $d$ 的选取。注意到在之前的算法中选取 $d$ 的常数倍并不会造成影响，因此考虑取若干个 $d$，能够覆盖到所有可能存在的 $d$ 的常数倍。显然 $2^0, 2^1, \dots, 2^{\lceil \log \max\{x_i, y_i\}\rceil}$ 满足要求。

于是枚举 $k = 0 \sim \lceil \log \max\{x_i, y_i\}\rceil$，将平面划分为大小为 $2^k \times 2^k$ 的网格，在此基础上开始考虑贡献。

对于每一块，只需要按编号排序，然后取相邻的计算贡献即可覆盖全部。对于相邻的两块，将两块的点同时按编号排序，可以发现有贡献的点对在排序后的序列上距离 $O(1)$，因此只需要枚举相邻的 $O(1)$ 个点对计算贡献即可覆盖全部。

此时问题转化为 $O(n \log \max\{x_i, y_i\})$ 次单点修改，$q$ 次矩形查询，直接套用扫描线 + 分块的 $O(n \log \max\{x_i, y_i\} + q \sqrt n)$ 做法即可。这里采用分块是因为修改次数过多，直接使用 $O((n \log \max\{x_i, y_i\} + q)\log n)$ 的做法在实际运行中速度更慢。

实现时取相邻的 $O(1)$ 大概需要取 $10$ 个，但是常数过大。可以在初始对所有的点整体随机平移一次/随机扰动每一格的边长以改变网格图的划分，然后只需要取 $3$ 个点左右就足以覆盖所有有贡献的点对。

代码：

#include <bits/stdc++.h>
int read (void)
{
	int x = 0; char ch = getchar();
	while (ch < '0' or ch > '9') ch = getchar();
	while (ch >= '0' and ch <= '9') x = x * 10 + ch - 48, ch = getchar();
	return x;
}
const int maxn = 1 << 18;
int n, q, S, bl[maxn], x[maxn], y[maxn], p[maxn]; std::vector<int> A[maxn];
long long t1[maxn], t2[maxn], ans[maxn]; std::vector<std::pair<int, int>> Q[maxn];
std::unordered_map<long long, std::pair<int, int>> pos;
long long id (int x, int y) {return x * (1LL << 30) + y;}
long long dis (int u, int v) {return 1LL * (x[u] - x[v]) * (x[u] - x[v]) + 1LL * (y[u] - y[v]) * (y[u] - y[v]);}
void add (int x, long long y) {t1[x] = std::min(t1[x], y); t2[bl[x]] = std::min(t2[bl[x]], y);}
long long ask (int x)
{
	long long w = 1LL << 60;
	for (int i = x; bl[i] == bl[x]; i++) w = std::min(w, t1[i]);
	for (int i = bl[x] + 1; i <= bl[n]; i++) w = std::min(w, t2[i]);
	return w;
}
signed main ()
{
	n = read(); q = read(); S = sqrt(n);
	for (int i = 1; i <= n; i++) x[i] = read(), y[i] = read(), bl[i] = (i - 1) / S + 1;
	for (int i = 1, l, r; i <= q; i++) l = read(), r = read(), Q[r].push_back({l, i}), ans[i] = 1LL << 60;
	for (int k = 0; k <= 27; k++)
	{
		std::iota(p + 1, p + n + 1, 1);
		std::sort(p + 1, p + n + 1, [&] (const int &a, const int &b) {return (x[a] >> k) == (x[b] >> k) ? (y[a] >> k) < (y[b] >> k) : (x[a] >> k) < (x[b] >> k);});
		for (int l = 1, r; l <= n; l = r + 1)
		{
			for (r = l; r < n and (x[p[r + 1]] >> k) == (x[p[l]] >> k) and (y[p[r + 1]] >> k) == (y[p[l]] >> k); r++) ;
			std::sort(p + l, p + r + 1); pos[id(x[p[l]] >> k, y[p[l]] >> k)] = {l, r};
			for (int i = l; i <= r; i++) for (int j = i + 1; j <= i + 3 and j <= r; j++) A[p[j]].push_back(p[i]);
		}
		for (int l = 1, r; l <= n; l = r + 1)
		{
			for (r = l; r < n and (x[p[r + 1]] >> k) == (x[p[l]] >> k) and (y[p[r + 1]] >> k) == (y[p[l]] >> k); r++) ;
			std::vector<int> vec;
			int px = x[p[l]] >> k, py = y[p[l]] >> k;
			std::vector<std::pair<int, int>> P = {{-1, 1}, {0, 1}, {1, 1}, {1, 0}};
			for (auto [dx, dy]: P) if (pos.count(id(px + dx, py + dy)))
			{
				auto [pl, pr] = pos[id(px + dx, py + dy)];
				std::vector<int> vec;
				vec.insert(vec.end(), p + l, p + r + 1);
				vec.insert(vec.end(), p + pl, p + pr + 1);
				std::inplace_merge(vec.begin(), vec.begin() + r - l + 1, vec.end());
				for (int i = 0; i < (int)vec.size(); i++) for (int j = i + 1; j <= i + 3 and  j < (int)vec.size(); j++) A[vec[j]].push_back(vec[i]);
			}
		}
		std::unordered_map<long long, std::pair<int, int>>().swap(pos);
	}
	for (int i = 1; i <= n; i++) t1[i] = t2[i] = 1LL << 60;
	for (int i = 1; i <= n; i++)
	{
		for (int p: A[i]) add(p, dis(p, i));
		for (auto [p, id]: Q[i]) ans[id] = std::min(ans[id], ask(p));
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}