「Nhk R2」大户爱的驿站 - 题解

标签与难度

标签: 数据结构, Fenwick树(树状数组), 二维偏序, 离线算法, 图论难度: 2200

题目大意喵~

大户爱酱开了 N 家驿站，每家驿站 i 都有一个位置 x_i 和一个海拔 h_i。

从驿站 i 到驿站 j 有一条驿路（可以理解为有向边 i -> j），当且仅当 x_i > x_j 并且 h_i > h_j。这是一个典型的二维偏序关系，喵~

现在有两家快递公司，要把所有的驿路瓜分掉。对于每一家驿站 i，我们关心：

a_{0,i} 和 b_{0,i}: 从 i 出发的驿路，分别被第一家和第二家公司垄断的数量。
a_{1,i} 和 b_{1,i}: 到达 i 的驿路，分别被第一家和第二家公司垄断的数量。

大户爱希望两家公司能和平共处，所以她想让所有驿站的“不平衡度”之和最小。这个不平衡度就是：

\sum_{i=1}^{N} \left( |a_{0,i} - b_{0,i}| + |a_{1,i} - b_{1,i}| \right)

之后还有 Q 次独立的询问。每次询问会临时增加一家新的驿站 N+1，给出它的位置 x_{N+1} 和海拔 h_{N+1}。我们需要对这 N+1 家驿站组成的系统，计算上述不平衡度之和的最小值。

解题思路分析

这道题看起来有点复杂，又是绝对值又是最小化的，但别怕，让我来把它一层层解开，喵~

关键洞察：简化目标函数

我们想最小化 |a_{0,i} - b_{0,i}|。对于驿站 i，它总的出度（出发的驿路总数）是固定的，我们称之为 out_degree(i)。显然，a_{0,i} + b_{0,i} = out_degree(i)。那么 b_{0,i} = out_degree(i) - a_{0,i}，代入绝对值里得到： |a_{0,i} - (out_degree(i) - a_{0,i})| = |2a_{0,i} - out_degree(i)|。

为了让这个值最小，a_{0,i} 应该尽可能接近 out_degree(i) / 2。

如果 out_degree(i) 是偶数，比如 2k，我们可以分配 a_{0,i} = k, b_{0,i} = k，这样差值就是 0。
如果 out_degree(i) 是奇数，比如 2k+1，我们最好分配 a_{0,i} = k, b_{0,i} = k+1 (或者反过来)，差值就是 1。

所以，|a_{0,i} - b_{0,i}| 的最小值就是 out_degree(i) \pmod 2。同理，|a_{1,i} - b_{1,i}| 的最小值是 in_degree(i) \pmod 2。

那么，最终的答案是不是就是把所有驿站的 out_degree(i) \pmod 2 和 in_degree(i) \pmod 2 加起来呢？

一开始可能会这么想，但这里有个小陷阱！我们对每条驿路 (u, v) 的分配，会同时影响 u 的出度和 v 的入度。我们能保证对所有驿站同时达到这个理想的最小差值吗？

图论魔法：驿路分配的真相

答案是：可以的！喵~ 这里涉及到一个漂亮的图论结论。

我们可以把这个问题模型化：想象一个大的二分图。左边有 N 个点 U_1, ..., U_N 代表发件处，右边有 N 个点 V_1, ..., V_N 代表收件处。如果存在一条从 i 到 j 的驿路，我们就在 U_i 和 V_j 之间连一条边。

现在，我们要给这个二分图里的每一条边定向。从 U_i 指向 V_j 表示驿路 (i, j) 分给公司1；从 V_j 指向 U_i 表示分给公司2。

a_{0,i} 就是 U_i 的出度。
b_{0,i} 就是 U_i 的入度。
a_{1,j} 就是 V_j 的入度。
b_{1,j} 就是 V_j 的出度。

|a_{0,i} - b_{0,i}| 就是 |d_{out}(U_i) - d_{in}(U_i)|。 |a_{1,j} - b_{1,j}| 就是 |d_{in}(V_j) - d_{out}(V_j)|。

有一个神奇的定理（关于图的定向）说：对于任何图（包括我们这个二分图），都存在一种边的定向方式，使得对于每个节点 v，其出度和入度之差 |d_{out}(v) - d_{in}(v)| 不超过1。由于 d_{out}(v) - d_{in}(v) 和 d_{out}(v) + d_{in}(v) = \text{degree}(v) 的奇偶性相同，所以这个最小差值其实就是 \text{degree}(v) \pmod 2。

这意味着，我们总能找到一种分配方案，使得每个驿站 i 的不平衡度恰好是 out_degree(i) \pmod 2 (对于发件) 和 in_degree(i) \pmod 2 (对于收件)。

所以，最终的目标函数被我们成功简化啦！总的最小不平衡度就是：

\text{TotalCost} = \sum_{i=1}^{N} \left( \text{out\_degree}(i) \pmod 2 + \text{in\_degree}(i) \pmod 2 \right)

处理询问：离线大法好！

问题变成了：每次加一个点，快速计算所有点的 out_degree 和 in_degree，然后求它们的奇偶性之和。如果每次询问都暴力 O(N) 重新计算所有点的度，总时间会是 O(NQ)，太慢了。我们需要更快的办法！

注意到询问是独立的，我们可以使用离线算法。把所有初始点和查询点放在一起处理。对于一个查询点 q = (x_q, h_q)，我们来分析总代价的变化。设 Cost_{orig} 是初始 N 个点的总代价。加入 q 后，新的总代价是 Cost_{new}。 Cost_{new} 由三部分构成：

原先 N 个点因为和 q 产生了新连接，它们的度数可能变化，导致它们的代价项 (degree \pmod 2) 变化。
新点 q 本身的代价 (out_degree(q) \pmod 2 + in_degree(q) \pmod 2)。
Cost_{orig}。

我们来分析第一部分的变化量 \Delta Cost。对于一个原先的点 i，如果它和 q 之间形成了新驿路 (i, q)，它的 out_degree 会加1。 out_degree(i) 从 v 变为 v+1，那么 (out_degree(i) \pmod 2) 的变化是 ((v+1) \pmod 2) - (v \pmod 2)。

如果 v 是偶数，变化是 1 - 0 = 1。
如果 v 是奇数，变化是 0 - 1 = -1。这个变化量可以统一写成 1 - 2 * (v \pmod 2)。

所以，总的变化量就是对所有与 q 产生新连接的点 i，累加 1 - 2 * (degree_i^{orig} \pmod 2)。这需要我们对满足特定二维偏序条件的点集，进行带权重的求和。这是一个经典的二维数点/范围查询问题。

我们可以用 树状数组 + 排序 的离线技巧来高效解决：

预计算: 先用 O(N \log N) 的时间计算出初始 N 个点的 out_degree 和 in_degree。
离线处理:
- 将所有初始点和查询点混合，按 x 坐标排序。
- 用一个树状数组（BIT）维护 h 坐标轴上的信息。
- 从左到右（或从右到左）扫描排好序的点。
- 遇到初始点，就在BIT的对应 h 位置更新信息。
- 遇到查询点，就在BIT中查询一个 h 的前缀/后缀和，得到所需的值。

具体来说，对于每个查询 q，我们需要4个值：

out_degree(q): q能到达的点数 (x_i < x_q, h_i < h_q)。
in_degree(q): 能到达 q 的点数 (x_i > x_q, h_i > h_q)。
\sum_{i: i \to q} (out_degree_i^{orig} \pmod 2): 计算与 q 相关的出度代价变化。
\sum_{i: q \to i} (in_degree_i^{orig} \pmod 2): 计算与 q 相关的入度代价变化。

这四组值都可以通过两次不同排序方向的离线扫描+树状数组来求得。得到这些值后，就能 O(1) 算出每个查询的答案啦！

代码实现

这是我根据上面的思路，精心重构的代码哦~ 喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

// 为了方便，我们用一个结构体来表示驿站和询问
struct Point {
    int id;
    int x, h;
    int type; // 0 for initial station, 1 for query
};

// 树状数组 (Fenwick Tree), 喵~
class FenwickTree {
private:
    std::vector<int> tree;
    int size;

public:
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}

    void add(int index, int value) {
        for (; index <= size; index += index & -index) {
            tree[index] += value;
        }
    }

    int query(int index) {
        int sum = 0;
        for (; index > 0; index -= index & -index) {
            sum += tree[index];
        }
        return sum;
    }
    
    int query_range(int left, int right) {
        if (left > right) return 0;
        return query(right) - query(left - 1);
    }
};

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, q;
    std::cin >> n >> q;

    std::vector<Point> initial_points(n);
    std::vector<Point> queries(q);
    std::vector<int> h_coords; // 用于离散化

    for (int i = 0; i < n; ++i) {
        initial_points[i].id = i;
        std::cin >> initial_points[i].x >> initial_points[i].h;
        h_coords.push_back(initial_points[i].h);
    }
    for (int i = 0; i < q; ++i) {
        queries[i].id = i;
        std::cin >> queries[i].x >> queries[i].h;
        h_coords.push_back(queries[i].h);
    }

    // --- 离散化海拔 h ---
    std::sort(h_coords.begin(), h_coords.end());
    h_coords.erase(std::unique(h_coords.begin(), h_coords.end()), h_coords.end());
    auto get_h_rank = [&](int h) {
        return std::lower_bound(h_coords.begin(), h_coords.end(), h) - h_coords.begin() + 1;
    };
    int max_h_rank = h_coords.size();
    for (int i = 0; i < n; ++i) initial_points[i].h = get_h_rank(initial_points[i].h);
    for (int i = 0; i < q; ++i) queries[i].h = get_h_rank(queries[i].h);

    // --- 预计算初始 N 个点的 out_degree 和 in_degree ---
    std::vector<int> out_degree(n), in_degree(n);
    
    // 计算 out_degree
    std::sort(initial_points.begin(), initial_points.end(), [](const Point& a, const Point& b) {
        return a.x > b.x;
    });
    FenwickTree bit_out(max_h_rank);
    for (const auto& p : initial_points) {
        out_degree[p.id] = bit_out.query(p.h - 1);
        bit_out.add(p.h, 1);
    }

    // 计算 in_degree
    std::sort(initial_points.begin(), initial_points.end(), [](const Point& a, const Point& b) {
        return a.x < b.x;
    });
    FenwickTree bit_in(max_h_rank);
    for (const auto& p : initial_points) {
        in_degree[p.id] = bit_in.query(p.h - 1);
        bit_in.add(p.h, 1);
    }
    
    // 恢复初始点的原始顺序（如果需要的话，这里按 id 排序）
    std::sort(initial_points.begin(), initial_points.end(), [](const Point& a, const Point& b) {
        return a.id < b.id;
    });

    // --- 计算初始代价 ---
    long long base_cost = 0;
    for (int i = 0; i < n; ++i) {
        base_cost += (out_degree[i] % 2);
        base_cost += (in_degree[i] % 2);
    }

    // --- 离线处理询问 ---
    std::vector<Point> all_events;
    for(const auto& p : initial_points) all_events.push_back({p.id, p.x, p.h, 0});
    for(const auto& p : queries) all_events.push_back({p.id, p.x, p.h, 1});

    std::vector<long long> ans(q);

    // 第一次扫描 (x 从大到小): 计算 q 的 in_degree 和相关代价变化
    std::sort(all_events.begin(), all_events.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x > b.x;
        return a.type < b.type; // 初始点优先处理
    });
    FenwickTree bit1_count(max_h_rank), bit1_out_parity(max_h_rank);
    for (const auto& event : all_events) {
        if (event.type == 0) { // 初始点
            bit1_count.add(event.h, 1);
            bit1_out_parity.add(event.h, out_degree[event.id] % 2);
        } else { // 查询点
            long long q_in_degree = bit1_count.query_range(event.h + 1, max_h_rank);
            long long sum_out_p = bit1_out_parity.query_range(event.h + 1, max_h_rank);
            ans[event.id] += (q_in_degree % 2); // 新点 q 的入度代价
            ans[event.id] += (q_in_degree - 2 * sum_out_p); // 原先点的出度代价变化
        }
    }

    // 第二次扫描 (x 从小到大): 计算 q 的 out_degree 和相关代价变化
    std::sort(all_events.begin(), all_events.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.type < b.type;
    });
    FenwickTree bit2_count(max_h_rank), bit2_in_parity(max_h_rank);
    for (const auto& event : all_events) {
        if (event.type == 0) { // 初始点
            bit2_count.add(event.h, 1);
            bit2_in_parity.add(event.h, in_degree[event.id] % 2);
        } else { // 查询点
            long long q_out_degree = bit2_count.query_range(event.h + 1, max_h_rank);
            long long sum_in_p = bit2_in_parity.query_range(event.h + 1, max_h_rank);
            ans[event.id] += (q_out_degree % 2); // 新点 q 的出度代价
            ans[event.id] += (q_out_degree - 2 * sum_in_p); // 原先点的入度代价变化
        }
    }
    
    // --- 输出最终结果 ---
    for (int i = 0; i < q; ++i) {
        std::cout << base_cost + ans[i] << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O((N+Q)\log(N+Q))$ 。
- 离散化需要排序，复杂度是 $O((N+Q)\log(N+Q))$ 。
- 预计算初始 N 个点的度，需要排序和树状数组操作，复杂度是 $O(N \log N)$ 。
- 离线处理询问是主要部分。我们将 N+Q 个事件排序，复杂度是 $O((N+Q)\log(N+Q))$ 。之后遍历事件，每次操作树状数组，复杂度是 $O(\log(\text{max\_h}))$ , 其中 max_h 是离散化后的坐标范围，最大为 N+Q。所以这部分总复杂度是 $O((N+Q)\log(N+Q))$ 。
- 最后计算答案是 O(Q)。
- 所以，总的时间瓶颈在于排序。
空间复杂度: $O(N+Q)$ 。
- 我们需要存储初始点、查询点和所有事件，空间是 $O(N+Q)$ 。
- 树状数组和离散化数组也需要 $O(N+Q)$ 的空间。

知识点总结

问题转化: 本题的核心在于将一个看似复杂的优化问题 min(|a-b|)，通过图论的视角（边的定向）转化为一个简单的求和问题 sum(degree % 2)。这是解题的最关键一步，喵！
二维偏序: 驿路存在的条件 x_i > x_j 且 h_i > h_j 是一个经典的二维偏序模型。这类问题通常可以通过 排序 + 数据结构 的方式解决。
离线算法: 当询问之间相互独立，且可以一次性读入时，离线处理是一个非常强大的思想。它允许我们通过排序来消除一个维度（比如 x 坐标），从而将问题降维，用更简单的数据结构（如树状数组）来处理另一个维度（h 坐标）。
树状数组 (Fenwick Tree): 它是解决动态前缀和问题的利器，特别适合在离线算法中处理一维的动态计数和求和。代码实现简单，常数小，是竞赛中的好朋友，的说！

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！喵~

「Nhk R2」大户爱的驿站 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键洞察：简化目标函数 ​

图论魔法：驿路分配的真相 ​

处理询问：离线大法好！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​