F1. Field Division (easy version) - 题解

比赛与标签

比赛: Codeforces Round 950 (Div. 3) 标签: data structures, math, sortings 难度: *1900

喵喵，这题要怎么分地呢？ (题目大意)

Alice和Bob要在一块超——大的 n x m 的田地里分家当啦！田地里有 k 个不能动的喷泉。

Alice需要画一条线来分地。这条线有几个规矩：

1. 只能从上边界或左边界的某个没有喷泉的格子出发。
2. 每一步只能向下或者向右移动一格。
3. 最终要走到下边界或者右边界。
4. 画出的这条线以及线左下方的区域都归Alice，右上方的区域归Bob。具体来说，Alice的地盘必须包含(n, 1)，Bob的地盘必须包含(1, m)。
5. 所有喷泉都必须在Bob的地盘里，也就是说Alice的路径不能经过任何一个喷泉所在的格子。

Alice当然是想让自己的地盘面积越大越好啦！

我们需要解决两个问题：

1. 计算 alpha: 在所有喷泉都归Bob的情况下，Alice能得到的最大地盘面积是多少？
2. 判断 a_i: 对于第 i 个喷泉，如果Bob把它送给Alice（也就是Alice不再需要避开这个喷泉了），Alice的最大地盘面积会不会增加？如果增加，a_i 就是 1，否则就是 0。

找到最优的边界喵！ (解题思路)

这道题的核心，就是帮Alice找到一条最优的分割线，让她的面积最大化。

1. 理解Alice的最优路径

Alice的路径只能向右和向下，形成一个“楼梯”形状的边界。为了让自己的面积（左下部分）最大，她肯定希望这条“楼梯”尽可能地靠右上角，对吧？

上图中，蓝色的区域是Alice的，为了最大化蓝色区域，红色的路径就要尽量往右上角挤。

2. 喷泉的约束

每个喷泉 (r, c) 就像一个障碍物。因为它必须在Bob的区域（右上方），所以Alice的路径在第 r 行以及更下方的所有行，都必须在第 c 列的左边。也就是说，对于一个喷泉 (r_f, c_f)，Alice路径上的任何一点 (r_p, c_p)，只要 r_p >= r_f，就必须满足 c_p < c_f。

为了让自己的面积最大化，Alice在每一行都会走到她能走到的最右边的格子。我们把在第 i 行，Alice能走到的最右列号称为 path_col(i)。那么Alice的总面积就是 sum(path_col(i)) for i from 1 to n。

3. 计算 alpha (所有喷泉都归Bob)

在第 r 行，path_col(r) 受到了所有行号 r_f <= r 的喷泉的限制。不对不对，是受到所有行号 r_f >= r 的喷泉的限制！因为路径是单调的，一旦到了第 r 行，就不能再往回走了。所以，在第 r 行的决策，会影响到后面所有行的路径。

一个更清晰的思路是：在第 r 行，Alice能走到的最右列 path_col(r)，取决于**当前行以及所有未来行（r 到 n）**的喷泉约束。 path_col(r) 必须小于所有在 r' >= r 的行上的喷泉的列坐标 c_f。

所以，我们可以定义一个“列限制” V'_r，代表只考虑第 r 行的喷泉时，路径允许的最右列。V'_r = min({m} U {c_f - 1 | 喷泉在(r, c_f)})。如果第 r 行没有喷泉，V'_r = m。

那么，在第 r 行，Alice实际能走到的最右列，是 min(V'_r, V'_{r+1}, ..., V'_n)。这是一个典型的后缀最小值问题！

我们可以高效地计算这个：

1. 先把所有喷泉按行号 r 分组。对于每个有喷泉的行 R_i，计算出该行最左边喷泉带来的列限制 V_i = min_c - 1。
2. 将这些 (R_i, V_i) 对按 R_i 从小到大排序。
3. 计算 V_i 的后缀最小值。我们用一个数组 C 来存，C[i] = min(V_i, V_{i+1}, ...)。这样，对于 R_{i-1} 到 R_i - 1 之间的所有行，它们的最优列宽都是 C[i]。
4. 现在可以分块计算总面积 alpha 啦！
   • 从第 1 行到 R_1 - 1 行，宽度是 C[1]。
   • 从第 R_1 行到 R_2 - 1 行，宽度是 C[2]。
   • ...
   • 最后从 R_p 行到 n 行，宽度是 m。 把这些矩形的面积加起来就是 alpha 啦！

4. 判断 a_i (移除喷泉的影响)

什么时候移除一个喷泉 f = (r, c) 会让Alice的面积增加呢？ 只有当这个喷泉是决定边界的关键瓶颈时，移除它才能放松限制，从而增加面积。

一个喷泉 f 是“关键瓶颈”需要满足三个条件，缺一不可喵：

1. 它是自己所在行的最左喷泉: f.c - 1 == V_r (这里的 V_r 是只考虑 r 行的列限制)。如果它不是最左边的，那么就算移除了它，V_r 也不会变，因为还有更左的喷泉限制着。
2. 它是自己所在行唯一的那个最左喷泉: 如果有好几个喷泉都在最左边的同一列，移走一个，还有别的在呀，V_r 还是不会变。
3. 它所在行的约束是当前段最严格的: V_r 必须比后面所有行的约束 C[r+1] 都更严格 (即 V_r < C[r+1])。如果 V_r 本来就比后面的约束要宽松，那实际的边界是由后面的喷泉决定的，移不移走 f 都没影响。

只有同时满足这三点，移除喷泉 f 才能让 V_r 变大，并且这个变大的 V_r 能够成功地将边界往右推，从而增加总面积。

代码实现喵~

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

// 用一个结构体来存放喷泉的信息，方便管理喵
struct Fountain {
    int r, c, id;
};

void solve() {
    long long n;
    long long m;
    int k;
    std::cin >> n >> m >> k;
    std::vector<Fountain> fountains(k);
    // 用 map 把喷泉按行号分组，方便处理同一行的喷泉
    std::map<int, std::vector<int>> row_to_cols;
    for (int i = 0; i < k; ++i) {
        std::cin >> fountains[i].r >> fountains[i].c;
        fountains[i].id = i;
        row_to_cols[fountains[i].r].push_back(fountains[i].c);
    }

    // R_V_pairs 存储每个有喷泉的行R和它对应的列限制V
    // V = min_c - 1，是该行最左喷泉决定的边界
    std::vector<std::pair<int, int>> R_V_pairs;
    // min_c_counts 记录每行最左喷泉的数量，用于后面的判断
    std::map<int, int> min_c_counts;
    for (auto const& [r, cols] : row_to_cols) {
        int min_c = m + 1;
        for (int c : cols) {
            min_c = std::min(min_c, c);
        }
        R_V_pairs.push_back({r, min_c - 1});
        int count = 0;
        for (int c : cols) {
            if (c == min_c) {
                count++;
            }
        }
        min_c_counts[r] = count;
    }

    // 按行号排序，方便我们从上到下处理
    std::sort(R_V_pairs.begin(), R_V_pairs.end());

    int p = R_V_pairs.size();
    std::vector<long long> C(p + 2);
    C[p + 1] = m; // 最后一个喷泉行之后，就没限制啦，可以到头

    // 计算后缀最小值，C[i] 是从第 R_V_pairs[i-1] 行开始的列限制
    for (int i = p; i >= 1; --i) {
        C[i] = std::min((long long)R_V_pairs[i - 1].second, C[i + 1]);
    }

    // 分块计算总面积 alpha
    long long alpha = 0;
    long long last_R = 0;
    for (int i = 0; i < p; ++i) {
        // 矩形面积 = 高度 * 宽度
        // 高度是 (当前喷泉行 - 上一个喷泉行)
        // 宽度是这个区间的列限制 C[i+1]
        alpha += (long long)(R_V_pairs[i].first - last_R) * C[i + 1];
        last_R = R_V_pairs[i].first;
    }
    // 加上最后一个喷泉行到 n 行的面积
    alpha += (n - last_R) * m;

    std::cout << alpha << "\n";

    std::vector<int> a(k);
    // 方便快速查找某一行在 R_V_pairs 中的索引
    std::map<int, int> R_to_idx;
    for(int i=0; i<p; ++i) {
        R_to_idx[R_V_pairs[i].first] = i + 1;
    }

    // 检查每个喷泉是否是“关键瓶颈”
    for (const auto& f : fountains) {
        auto it = R_to_idx.find(f.r);
        // 这不应该发生，因为每个喷泉都在一个有喷泉的行里
        if (it == R_to_idx.end()) { 
            a[f.id] = 0;
            continue;
        }
        int s = it->second; // 喷泉 f 所在行的索引
        long long V_s = R_V_pairs[s - 1].second; // 该行的列限制

        // 同时满足三个条件，才是关键喷泉！
        // 1. f.c - 1 == V_s: 它是最左的喷泉之一
        // 2. min_c_counts[f.r] == 1: 它是唯一的最左喷泉
        // 3. V_s < C[s + 1]: 它所在行的限制比后面的都严格
        if (f.c - 1 == V_s && min_c_counts[f.r] == 1 && V_s < C[s + 1]) {
            a[f.id] = 1;
        } else {
            a[f.id] = 0;
        }
    }

    for (int i = 0; i < k; ++i) {
        std::cout << a[i] << (i == k - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析喵

• 时间复杂度: O(k log k) 的说。
  • 主要的耗时在对 k 个喷泉进行分组（用map是 O(k log k)）和对 p (p <= k) 个喷泉行约束进行排序（O(p log p)）。其他部分比如计算后缀最小值和遍历喷泉都是线性的。所以总的复杂度由排序主导，是 O(k log k) 呐。
• 空间复杂度: O(k) 的说。
  • 我们需要存储 k 个喷泉的信息，以及一些辅助的map和vector，它们的大小都和喷泉数量 k 或者有喷泉的行数 p 成正比，所以空间复杂度是 O(k)。

知识点与总结的说！

这道题真有趣，把一个看起来很复杂的几何问题，一步步转换成了我们熟悉的算法模型！

1. 问题转化: 核心就是把最大化二维面积的问题，转化成了一维的后缀最小值问题。我们通过分析路径的最优性质，发现每一行的最优宽度只受未来行的约束，这是一个非常重要的洞察！
2. 后缀最小值: 这是一个处理“未来约束”问题的经典技巧。当序列中一个点的取值受到它后面所有点的影响时，就可以考虑用后缀（或前缀）信息来优化计算。
3. 关键因素分析: 解决第二问的关键在于分析什么因素的改变会引起最终结果的改变。通过倒推 alpha 的计算过程，我们能准确地定位到那三个决定性的条件，这是解题的精髓所在！
4. 编程技巧: 使用 std::map 来按行分组，可以很方便地处理同一行的所有喷泉，代码会变得很清晰。同时要注意 n, m 很大，面积 alpha 可能会爆 int，记得用 long long 哦！

希望这篇题解能帮到大家！解题就像寻宝一样，只要思路对了，总能找到答案的！大家要继续加油哦，喵~！