题解：AT_abc366_e [ABC366E] Manhattan Multifocal Ellipse

· · 题解

写在前面的话

本篇题解篇幅较长，但是如果你想彻底把这道题弄懂，请静下心来，把这篇题解看完，相信对你的提升会很大。如果有看不懂的地方欢迎给我发私信，我会详细地解答。

题目简述

平面上有 n 个点 (x_i,y_i)，求有多少个点 (x,y) 满足这 n 个点到它的哈夫曼距离之和不超过 D。

后面半句话也就是，\sum_{i=1}^n(|x-x_{i}|,|y-y_{i}|) \le D。

思路

对上式进行变形：

\sum_{i=1}^n|y-y_i|\le D-\sum_{i=1}^n|x-x_i|

我们可以枚举所有的 x，带入上式右边，然后计算有多少个 y 满足。

实现

枚举 x 的坐标的话，我们需要实现 \Theta(1) 查询 \sum_{i=1}^n|x-x_i|。

思考 x 坐标每往右移 1，它对答案的影响会发生什么，什么会导致它发生变化。

这里先说结论，从点 p，到 p+1 它对答案的变化是点 p+1 右边有多少个 x_i，减去左边有多少个 x_i。

更为形式化的，设之前的答案为 old，现在的答案 now，点 p+1 的左边有 l 个满足条件的 x_i，右边有 r 个满足条件的，那么 now=old-l+r。

为什么这么做可以？

看图，其中黄色点是 x_i，蓝色点是 p，红色点是 p+1，蓝色线是 p 所有 x_i 到它的距离之和，也就是我们要算的东西，红色点同理。

从图中我们可以直观的看到从点 p 到 p+1，红点左侧的每条线段长度都比之前长了 1，右边的线段长度都减少了 1。左边有两个点就减少 2，右边 3 个点就增加 3。

和我们的结论是一样的。

第一个问题已经解决了，我们还需要 \Theta(1) 求出有多少个 y 满足式子。

预处理所有的 y 的值，用算 x 的方法求出 \sum_{i=1}^n|y-y_i| 的值，放进一个桶里，然后进行前缀和，就行了。

这里这道题也就讲完了。

最后总结一下算法流程：

  1. 预处理所有 y 的可能值，放进桶里，前缀和。

  2. 用类似的办法，枚举 x 的可能值，对每个 x 算出有多少个 y 满足条件。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 6e6 + 10;
int x[maxn], y[maxn];
int cnt[maxn], sum[maxn];
int mpx[maxn], mpy[maxn];
signed main()
{
    int n, d;
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> x[i] >> y[i];
        mpx[x[i] + 2000000]++, mpy[y[i] + 2000000]++;
    }
    int now = 0, l = 0, r = n, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        now += abs((-(2e6 + 1)) - y[i]);
    }
    for (int i = -2e6; i <= 2e6; i++)
    {
        now += l, now -= r;
        if (now <= d)
            cnt[now]++;
        l += mpy[i + 2000000], r -= mpy[i + 2000000];
    }
    for (int i = 0; i <= d; i++)
    {
        sum[i] = sum[i - 1] + cnt[i];
    }
    now = 0, l = 0, r = n;
    for (int i = 1; i <= n; i++)
    {
        now += abs(-(2e6 + 1) - x[i]);
    }
    for (int i = -2e6; i <= 2e6; i++)
    {
        now += l, now -= r;
        if (now <= d)
            ans += sum[d - now];
        l += mpx[i + 2000000], r -= mpx[i + 2000000];
    }
    cout << ans;
    return 0;
}