题解 | #求最值#

定理（最近点对分治算法的合并步骤复杂度）

设：

• 是平面上 个点的集合，且所有点的 坐标均不同。
• 在分治算法中，递归处理左右子集后，已得到左右两部分点对之间的最小距离 。
• 设 为分割左右子集的中线 坐标。
• 令 为 中所有与中线 的垂直距离（即 ）小于 的点构成的子集，并按 坐标升序排序。

则： 对于 中按 坐标排序后的任意一点 ，在排序列表中位于 之后且可能与 构成距离小于 的点对（即满足 的点 ）的数量不超过 6 个。

换言之，在合并步骤中，为寻找可能更新最小距离 的跨分割线点对，只需对 中的每个点 ，检查其后续最多 6 个点即可。这保证了合并步骤可以在 时间内完成，而由于 是 的，整个分治算法的合并步骤总体复杂度为 。

补充说明与推论

1. 常数的由来：数字“6”是一个紧确上界。它是通过将 所在的、宽度为 的垂直长条，划分为若干个 的小方格，并运用鸽巢原理证明得到的。每个这样的小方格内至多包含一个点（否则与 是左右子集的最小距离矛盾），而一个 的矩形最多能容纳7个这样的不重叠小方格，除去点 自身所在的位置，最多还需检查6个。

2. 算法表述：基于此定理，最近点对分治算法的合并步骤可描述为：

   1. 构建点集 。
   2. 将 按 坐标排序（通常通过归并递归结果在 时间内完成）。
   3. 对 中的每个点 （按 升序），计算其与后续点 （）的距离，一旦 或已检查完 之后的6个点，则停止对 的检查。
   4. 用所有找到的小于 的距离更新全局最小距离。

3. 算法总复杂度：该定理保证了合并步骤的线性复杂度，从而使整个分治算法满足递归式 。根据主定理，算法总时间复杂度为 。

总结：此定理是最近点对分治算法高效性的核心，它严格证明了在合并阶段只需进行常数次比较，从而将看似需要 的暴力比较优化至 。

#include <bits/stdc++.h>
using namespace std;
    typedef long long LL;
    const LL INF = 1e18;

    struct Point
    {
        LL x, y; // x是下标i，y是前缀和prefix[i]
        Point(LL _x = 0, LL _y = 0) : x(_x), y(_y) {}
    };

    // 比较函数：按x坐标排序
    bool cmpx(const Point &a, const Point &b)
    {
        return a.x < b.x;
    }

    // 比较函数：按y坐标排序
    bool cmpy(const Point &a, const Point &b)
    {
        return a.y < b.y;
    }

    // 计算两点距离的平方
    LL dist2(const Point &a, const Point &b)
    {
        LL dx = a.x - b.x;
        LL dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    // 分治法求最近点对距离的平方
    // points已经按x坐标排序
    LL closestPair(vector<Point> & points, int left, int right)
    {
        if (left >= right)
            return INF;
        if (left + 1 == right)
        {
            // 只有两个点，直接计算距离
            if (points[left].y > points[right].y)
            {
                swap(points[left], points[right]);
            }
            return dist2(points[left], points[right]);
        }

        int mid = (left + right) / 2;
        LL midX = points[mid].x;

        // 递归求解左右两半
        LL d = min(closestPair(points, left, mid), closestPair(points, mid + 1, right));

        // 合并：将左右两半按y坐标归并排序
        inplace_merge(points.begin() + left, points.begin() + mid + 1,
                      points.begin() + right + 1, cmpy);

        // 收集x坐标在[midX - sqrt(d), midX + sqrt(d)]范围内的点
        // 为了免去开方，我们比较平方值
        vector<Point> strip;
        for (int i = left; i <= right; i++)
        {
            LL dx = points[i].x - midX;
            if (dx * dx < d)
            {
                strip.push_back(points[i]);
            }
        }

        // 检查strip中的点对
        int m = strip.size();
        for (int i = 0; i < m; i++)
        {
            // 每个点最多只需要检查后面6个点
            for (int j = i + 1; j < m && j <= i + 7; j++)
            {
                LL dy = strip[j].y - strip[i].y;
                if (dy * dy >= d)
                    break; // 如果y坐标差已经太大，后面的点距离更大
                d = min(d, dist2(strip[i], strip[j]));
            }
        }

        return d;
    }

    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);

        int n;
        cin >> n;

        vector<Point> points(n + 1); // 使用1-based索引
        vector<LL> prefix(n + 1, 0);

        // 读取数据并计算前缀和
        for (int i = 1; i <= n; i++)
        {
            LL val;
            cin >> val;
            prefix[i] = prefix[i - 1] + val;
            points[i] = Point(i, prefix[i]); // 点(i, prefix[i])
        }

        // 移除points[0]，我们只需要1到n的点
        points.erase(points.begin());

        // 点集已经按x坐标（下标i）有序
        LL ans = closestPair(points, 0, n - 1);

        cout << ans << endl;

        return 0;
    }