E. Reverse the Rivers - 题解

比赛与标签

比赛: Codeforces Round 984 (Div. 3) 标签: binary search, constructive algorithms, data structures, greedy 难度: *1600

题目大意喵~

主人你好呀~ 来看这道有趣的题目喵！(ฅ'ω'ฅ)

这道题是说，有 n 个国家，每个国家有 k 个地区。水会从编号小的国家流向编号大的国家。对于第 j 个地区，第 i 个国家的水量 b[i][j] 会变成从第 1 个国家到第 i 个国家在该地区初始水量 a[...][j] 的按位或 (bitwise OR) 之和。也就是 b[i][j] = a[1][j] | a[2][j] | ... | a[i][j]。

然后呢，会有 q 次查询。每次查询会给出 m 个要求，每个要求形如 (r, o, c)，表示我们选择的国家 i 必须满足：

• 如果符号 o 是 <，那么第 r 个地区的水量要 b[i][r] < c。
• 如果符号 o 是 >，那么第 r 个地区的水量要 b[i][r] > c。

我们需要找到满足所有 m 个要求的最小的国家编号 i。如果找不到，就输出 -1 呐。

解题思路喵！

这道题的查询次数和要求总数都挺大的，如果每次查询都暴力去检查每个国家，肯定会超时的说。所以我们需要一个更聪明的办法！

关键观察：单调性！

我们来康康水量 b[i][j] 的计算公式：b[i][j] = a[1][j] | ... | a[i][j]。 那么 b[i+1][j] 是什么呢？是 b[i][j] | a[i+1][j] 呀！ 因为按位或运算的性质，一个数或上另一个数，结果永远不会变小。所以 b[i+1][j] >= b[i][j] 总是成立的！

这意味着，对于任何一个固定的地区 j，水量 b[1][j], b[2][j], ..., b[n][j] 是一个 非递减 的序列！ 哇！一旦有了单调性，我们最喜欢的 二分查找 就可以登场啦！喵~

预处理大法

因为每次查询都要用到 b 数组，而 b 数组是固定的，所以我们可以先花一点时间把所有 b[i][j] 的值都算出来，存起来。这个过程叫做预处理。

我们可以创建一个二维数组 prefix_or[k][n]，其中 prefix_or[j][i] 就存放第 j+1 个地区到第 i+1 个国家的水量之和（注意代码里是0-indexed，所以要对应好哦）。计算这个只需要 O(n*k) 的时间。

处理查询：范围缩紧术！

现在，对于每一次查询，我们有一堆要求。我们的目标是找到一个国家 i，它能满足所有要求。 我们可以把所有可能的国家 [1, n] 看作一个候选范围。然后，用每个要求来“修剪”这个范围，直到找到最终的答案！

1. 初始化：我们先假设所有国家都可能是答案，所以我们的答案范围是 [L, R] = [1, n]。

2. 逐个处理要求：对于每个要求 (r, o, c)：

   • 情况一：b[i][r] < c 因为 b 数组在 i 这个维度上是单调的，我们可以用二分查找（比如 std::lower_bound）在 prefix_or[r-1] 这个数组里找到第一个大于等于 c 的位置。假设这个位置的索引是 idx。那么所有索引小于 idx 的国家（也就是国家 1 到 idx）都满足 b[i][r] < c。这个要求就把我们答案的上界限制在了 idx。所以我们需要更新 R = min(R, idx)。
   • 情况二：b[i][r] > c 类似地，我们可以用二分查找（比如 std::upper_bound）找到第一个严格大于 c 的位置，假设索引是 idx。那么从这个国家开始，后面的所有国家（也就是国家 idx+1 到 n）都满足 b[i][r] > c。这个要求就把我们答案的下界限制在了 idx+1。所以我们需要更新 L = max(L, idx+1)。

3. 最终答案：在处理完所有 m 个要求后，我们就得到了一个最终的候选范围 [L, R]。

   • 如果 L > R，说明没有国家能同时满足所有要求，范围被“修剪”空了，答案就是 -1。
   • 如果 L <= R，那么 L 就是满足所有条件的最小国家编号，直接输出 L 就好啦！

这个方法，对于每个要求都只需要一次二分查找 O(log n) 的时间，是不是超级高效的说！

代码实现喵~

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 加速输入输出，让程序跑得飞快喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q;
    cin >> n >> k >> q;
    vector<vector<int>> a(n, vector<int>(k));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            cin >> a[i][j];
        }
    }

    // 预处理部分：计算每个地区的前缀或
    // OR[j][i] 存储的是第 j+1 个地区，从国家 1 到国家 i+1 的按位或结果
    vector<vector<int>> OR(k, vector<int>(n));
    for (int j = 0; j < k; j++) {
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur |= a[i][j];
            OR[j][i] = cur;
        }
    }

    // 处理 q 次查询
    while (q--) {
        int m;
        cin >> m;
        
        // 初始化答案的可能范围是 [1, n]
        int L_ans = 1, R_ans = n;
        
        for (int i = 0; i < m; i++) {
            int r;
            char op;
            int c;
            cin >> r >> op >> c;
            r--; // 转换为 0-indexed

            // 如果当前范围已经无效，就没必要继续处理了
            if (L_ans > R_ans) {
                continue;
            }
            
            if (op == '<') {
                // 我们需要 b[i][r] < c
                // lower_bound 找到第一个 >= c 的元素
                auto it = lower_bound(OR[r].begin(), OR[r].end(), c);
                // it - begin() 得到的是 0-indexed 的国家索引
                int idx0 = it - OR[r].begin();
                // 所以满足条件的国家是 1 到 idx0
                int L_req = 1;
                int R_req = idx0; 
                // 更新总的答案范围，取交集
                L_ans = max(L_ans, L_req);
                R_ans = min(R_ans, R_req);
            } else if (op == '>') {
                // 我们需要 b[i][r] > c
                // upper_bound 找到第一个 > c 的元素
                auto it = upper_bound(OR[r].begin(), OR[r].end(), c);
                int idx0 = it - OR[r].begin();
                // 满足条件的国家是 idx0+1 到 n
                int L_req = idx0 + 1;
                int R_req = n;
                // 更新总的答案范围，取交集
                L_ans = max(L_ans, L_req);
                R_ans = min(R_ans, R_req);
            }
        }
        
        // 如果最终范围有效，输出最小的可能答案 L_ans
        if (L_ans <= R_ans) {
            cout << L_ans << '\n';
        } else {
            // 否则没有找到合适的国家
            cout << -1 << '\n';
        }
    }

    return 0;
}

复杂度分析的说

• 时间复杂度: O(n * k + sum(m) * log n) 的说。

  • 预处理计算 OR 数组需要 O(n * k) 的时间。
  • 对于所有的 q 次查询，总共有 sum(m) 个要求。每个要求我们都在一个长度为 n 的数组上做一次二分查找，耗时 O(log n)。所以查询部分的总时间是 O(sum(m) * log n)。
  • 两部分加起来就是总时间复杂度啦，完全可以接受！

• 空间复杂度: O(n * k) 的说。

  • 我们主要需要存储初始的 a 数组和预处理的 OR 数组，它们的大小都是 n * k 级别的。

知识点与总结

这道题真是一次愉快的思维体操呢！(≧▽≦)

1. 挖掘单调性: 解决问题的突破口在于发现 b[i][j] 关于 i 的非递减性。在算法竞赛中，看到前缀和、前缀积、前缀OR/AND/XOR这类结构，一定要立刻想想它是否具有单调性或者其他可以利用的数学性质！
2. 预处理思想: “预磨刀不误砍柴工”。对于那些在多次查询中反复使用的、固定不变的数据，提前计算好是一种非常经典和有效的优化策略。
3. 二分查找的应用: std::lower_bound 和 std::upper_bound 是 C++ STL 中非常强大的工具，它们能帮助我们在有序（或单调）序列中快速定位，是实现这类查找问题的完美选择。
4. 区间交集: 当一个问题需要同时满足多个条件时，可以考虑将每个条件转化为对解的一个区间限制，然后通过求所有区间的交集来找到最终的解集。维护一个 [L, R] 区间并不断收缩它，就是实现这个思想的常用方法。

喵~ 希望这篇题解能帮到主人哦！继续加油，你超棒的！如果有其他问题，随时可以再来找我玩呀！