ABC366E Manhattan Multifocal Ellipse

Tag：前缀和

题目描述

给定二维平面上的 \(N\) 个点 \((x_1,y_1),(x_2,y_2), \cdots ,(x_i,y_i)\)，以及一个非负整数 \(D\)。

找出满足 \(\sum_{i=1}^n (|x - x_i| + |y - y_i|) \leq D\) 的 \((x,y)\) 整数对有多少个。

数据说明：

\(1 \leq N \leq 2 \times 10^5\)
\(0 \leq D \leq 10^6\)
\(-10^6 \leq x_i, y_i \leq 10^6\)
\((x_i, y_i) \neq (x_j, y_j)\) for \(i \neq j\).

分析

首先观察 \(\displaystyle\sum_{i=1}^n (|x - x_i| + |y - y_i|)\)，这个式子是可以拆成 \(\displaystyle\sum_{i=1}^n |x - x_i| + \displaystyle\sum_{i=1}^n |y - y_i|\)，因此 \(x,y\) 是可以分开独立计算的。

我们先考虑 \(x\)，当我们枚举到一个点的时候，他与其他所有点的距离为 \(\displaystyle\sum_{i=1}^n |x - x_i|\)。我们找一个最大的 \(tmp\) 使得 \(x_{tmp} < x\)。把绝对值拆开则有 \(\displaystyle\sum_{i=1}^{tmp} (x - x_i) + \displaystyle\sum_{i=tmp+1}^n (x_i - x)\)。我们开一个桶 \(ansX\) 把答案记录下来。

对于 \(y\) 同理，做一个 \(ansY\) 的桶把答案记录下来。

对于 \(ansY\) 做一个前缀和，记这个前缀和为 \(p\)。

最后我们要计算的答案为 \(\displaystyle\sum_{i=0}^m X_i \times p_{m-i}\)。

记得开 \(long long\)。

代码实现

const int N = 1e6 + 5;
int bukX[N * 4],bukY[N * 4];
int ansX[N],ansY[N];
void NeverSayNever() {
    int n, D;
    cin >> n >> D;
    vector<int> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        bukX[x[i] + 2000000]++;
        bukY[y[i] + 2000000]++;
    }
    std::sort(x.begin() + 1, x.end());
    std::sort(y.begin() + 1, y.end());
    for (int i = 1; i <= 4e6; ++i) {
        bukX[i] += bukX[i - 1];
        bukY[i] += bukY[i - 1];
    }
    vector<int> preX(n + 1), preY(n + 1);
    for (int i = 1; i <= n; ++i) {
        preX[i] = preX[i - 1] + x[i] + 2000000;
        preY[i] = preY[i - 1] + y[i] + 2000000;
    }
    for (int i = 0; i <= 4e6; ++i) {
        int cur = bukX[i];
        int l = preX[cur], r = preX[n] - preX[cur];
        int cnt = r - (n - cur) * i + cur * i - l;
        if (cnt > D) continue;
        ansX[cnt]++;
    }
    for (int i = 0; i <= 4e6; ++i) {
        int cur = bukY[i];
        int l = preY[cur], r = preY[n] - preY[cur];
        int cnt = r - (n - cur) * i + cur * i - l;
        if (cnt > D) continue;
        ansY[cnt]++;
    }
    for (int i = 1; i <= D ; ++i) {
        ansY[i] += ansY[i - 1];
    }
    int ans = 0;
    for (int i = 0; i <= D ; ++i) {
        ans += ansX[i] * ansY[D - i];
    }
    cout << ans << endl;
}

日志

本页面创建于 2024/09/02 15:44

特别鸣谢：

Urtusea的细心指导