E. Domino Principle - 题解

比赛与标签

比赛: Codeforces Beta Round 52 (Div. 2) 标签: binary search, data structures, sortings 难度: *2200

题目大意喵~

主人你好呀~！(ฅ'ω'ฅ) 这道题是关于推倒多米诺骨牌的呐！

我们有一排 n 个多米诺骨牌，它们的高度各不相同。每个骨牌 i 都有一个坐标 x_i 和一个高度 h_i。

当我们向右推倒第 i 个骨牌时，它会倒下。如果一个坐标为 x、高度为 h 的骨牌倒下，它会触发所有位于 [x + 1, x + h - 1] 区间内的其他骨牌也跟着倒下。这是一个连锁反应哦！

我们的任务是，对于每一个骨牌，计算出如果从它开始推，总共会有多少个骨牌（包括它自己）倒下。

输入:

• 第一行是一个整数 n，表示骨牌的数量。
• 接下来 n 行，每行是两个整数 x_i 和 h_i。

输出:

• 一行 n 个数字，按照输入顺序，分别表示从第 i 个骨牌开始推倒会倒下的骨牌总数。

解题思路喵~

这道题看起来像是一个连锁反应问题，直接模拟每个骨牌的连锁反应肯定会超时的说。所以，我们需要找到更聪明的办法，这通常意味着要使用动态规划（DP）哦！

第一步：排序！

骨牌的坐标 x_i 是乱序的，这让我们很难处理它们之间的关系。一个非常自然的想法就是，先把所有骨牌按照坐标 x 从小到大排个序。这样一来，骨牌们就整整齐齐地从左到右排列好了，处理起来就方便多啦！当然，我们也要记下它们最开始的顺序（id），这样才能按原顺序输出答案喵~

第二步：从右向左的动态规划

让我们来定义一个状态。如果我们从左往右处理，计算推倒第 i 个骨牌会发生什么，会发现它依赖于它右边（j > i）的骨牌。这种依赖“未来”状态的 DP，通常可以倒过来思考，也就是从右往左进行计算！

于是，我们定义一个 M[i]：表示如果推倒第 i 个骨牌，它所引发的连锁反应能到达的最远坐标是多少。

当我们计算 M[i] 时，所有 M[j] (其中 j > i) 都已经被计算出来了，这真是太棒了！

现在我们来推导状态转移方程：

1. 首先，第 i 个骨牌自己倒下，能直接碰倒的最远范围是 dominoes[i].x + dominoes[i].h - 1。
2. 它还会碰倒所有在 (dominoes[i].x, dominoes[i].x + dominoes[i].h) 这个开区间内的骨牌。假设这些被直接碰倒的骨牌的索引范围是 i+1 到 k。
3. 这些从 i+1 到 k 的骨牌倒下后，它们各自也会引发连锁反应。我们已经计算出了它们各自能到达的最远坐标，即 M[i+1], M[i+2], ..., M[k]。
4. 所以，从第 i 个骨牌开始的整个连锁反应，能到达的最远坐标就是它自己能达到的，以及它碰倒的所有骨牌能达到的最远坐标中的最大值。

公式就是： M[i] = max( dominoes[i].x + dominoes[i].h - 1, max(M[i+1], M[i+2], ..., M[k]) )

第三步：数据结构优化！

哇，这个 max(M[i+1], ..., M[k]) 是一个区间最大值查询！如果每次都暴力遍历，总时间复杂度会是 O(n²)，肯定是不行的说。

这种问题，就是我们聪明的线段树大显身手的时候啦！我们可以用一个线段树来维护 M 数组，这样每次查询区间最大值就只需要 O(log n) 的时间。

所以，我们的算法流程（第一部分）就清晰了：

1. 从 i = n-1 循环到 0。
2. 对于当前的骨牌 i，它能直接碰倒的骨牌 j 满足 dominoes[j].x < dominoes[i].x + dominoes[i].h。我们可以用二分查找（比如 std::upper_bound）在排好序的骨牌数组中快速找到最右边的那个骨牌 k。
3. 如果 k > i，我们就在线段树中查询区间 [i+1, k] 的最大值 max_M_in_range。
4. 计算 M[i] = max(dominoes[i].x + dominoes[i].h - 1, max_M_in_range)。
5. 将计算出的 M[i] 更新到线段树的第 i 个位置上。

第四步：计算最终答案

当我们从右到左计算完所有的 M[i] 之后，M[i] 就代表了从第 i 个骨牌开始推倒的最终影响范围。

现在，对于每个 i，我们要计算有多少个骨牌会倒下。这其实就是问：从第 i 个骨牌开始（包括 i），有多少个骨牌 j 的坐标 dominoes[j].x 小于等于 M[i]？

因为我们的骨牌数组是按 x 坐标排好序的，所以我们又可以愉快地使用二分查找（std::upper_bound）啦！对于每个 i，我们找到第一个坐标大于 M[i] 的骨牌的位置，这个位置的索引减去 i，就是倒下的骨牌数量。

最后，把算出的数量根据之前保存的 id 存到答案数组里，再一起输出就好啦！完美~ (≧∀≦)♪

代码实现喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

// 骨牌结构体，保存坐标、高度和原始ID
struct Domino {
    int x, h, id;
};

// 线段树，用于存储区间最大值
std::vector<long long> tree;
int N_dominoes;

// 更新线段树中一个点的值
void update(int v, int tl, int tr, int pos, long long new_val) {
    if (tl == tr) {
        tree[v] = new_val;
    } else {
        int tm = tl + (tr - tl) / 2;
        if (pos <= tm) {
            update(v * 2, tl, tm, pos, new_val);
        } else {
            update(v * 2 + 1, tm + 1, tr, pos, new_val);
        }
        tree[v] = std::max(tree[v * 2], tree[v * 2 + 1]);
    }
}

// 查询线段树中一个区间 [l, r] 的最大值
long long query(int v, int tl, int tr, int l, int r) {
    if (l > r) {
        // 如果查询区间无效，返回一个极小值
        return -3e9; 
    }
    if (l == tl && r == tr) {
        return tree[v];
    }
    int tm = tl + (tr - tl) / 2;
    long long left_max = query(v * 2, tl, tm, l, std::min(r, tm));
    long long right_max = query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r);
    return std::max(left_max, right_max);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;
    N_dominoes = n;

    std::vector<Domino> dominoes(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> dominoes[i].x >> dominoes[i].h;
        dominoes[i].id = i; // 保存原始索引
    }

    // 按照 x 坐标排序
    std::sort(dominoes.begin(), dominoes.end(), [](const Domino& a, const Domino& b) {
        return a.x < b.x;
    });

    // 初始化线段树和M数组
    tree.assign(4 * N_dominoes, -3e9);
    std::vector<long long> M(n);
    std::vector<int> ans(n);

    // 从右向左进行动态规划
    for (int i = n - 1; i >= 0; --i) {
        // 计算当前骨牌能直接碰倒的最远坐标
        long long reach = (long long)dominoes[i].x + dominoes[i].h - 1;

        // 使用二分查找找到被当前骨牌碰倒的最右边的骨牌 k
        auto it = std::upper_bound(dominoes.begin() + i + 1, dominoes.end(), reach, 
            [](long long val, const Domino& d) {
                return val < d.x;
            });
        int k = std::distance(dominoes.begin(), it) - 1;

        long long current_M;
        if (k > i) {
            // 如果能碰倒其他骨牌，查询[i+1, k]区间的最大M值
            long long max_M_in_range = query(1, 0, n - 1, i + 1, k);
            current_M = std::max(reach, max_M_in_range);
        } else {
            // 如果碰不倒其他骨牌，M值就是它自己的reach
            current_M = reach;
        }
        M[i] = current_M;
        // 更新线段树
        update(1, 0, n - 1, i, M[i]);
    }

    // 计算最终答案
    for (int i = 0; i < n; ++i) {
        long long final_reach = M[i];
        // 使用二分查找找到所有被推倒的骨牌
        auto it = std::upper_bound(dominoes.begin() + i, dominoes.end(), final_reach,
            [](long long val, const Domino& d) {
                return val < d.x;
            });
        // 计算数量
        int count = std::distance(dominoes.begin() + i, it);
        // 根据原始id存入答案数组
        ans[dominoes[i].id] = count;
    }

    // 按原始顺序输出答案
    for (int i = 0; i < n; ++i) {
        std::cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

复杂度分析喵~

• 时间复杂度: O(N log N) 的说。

  • 首先，对骨牌进行排序需要 O(N log N) 的时间。
  • 然后，我们有一个从右到左的循环，共 N 次。在循环内部，upper_bound (二分查找) 需要 O(log N)，线段树的查询和更新也都是 O(log N)。所以这一部分是 O(N log N)。
  • 最后计算答案的循环也是 N 次，每次调用 upper_bound，又是 O(N log N)。
  • 所以总的时间复杂度就是 O(N log N) 啦！非常高效！

• 空间复杂度: O(N) 的说。

  • 我们需要存储骨牌信息的 dominoes 数组，大小为 O(N)。
  • 存储DP结果的 M 数组和答案 ans 数组也是 O(N)。
  • 线段树 tree 的大小是 4N，所以也是 O(N)。
  • 总的空间复杂度是 O(N)，完全可以接受喵~

知识点与总结

这真是一道融合了多种算法思想的有趣题目呢！让本猫娘来总结一下吧~

1. 核心思想: 动态规划 + 数据结构优化。这是一个非常经典的解题模式！当你发现一个DP的状态转移涉及到区间查询或更新时，就要立刻想到用线段树、树状数组等数据结构来加速它。
2. DP设计技巧: 逆向思维。当DP状态 dp[i] 依赖于 dp[j] (其中 j > i) 时，不妨试试从后往前计算，问题可能就迎刃而解了。
3. 二分查找的应用: 在有序数组中查找满足特定条件的边界，二分查找是我们的不二之选！这道题里两次使用 std::upper_bound 来确定范围，是保持 O(N log N) 复杂度的关键。
4. 编程细节:
   • 保存原始ID: 排序前一定要记得保存元素的原始位置，否则最后无法按正确顺序输出。
   • 数据类型: 坐标 x 和高度 h 的值都很大，它们的和可能会超出 int 的范围，所以计算 reach 和 M 值时要使用 long long，防止溢出哦！

希望这篇题解能帮助到你！只要理清思路，一步步分解问题，再难的题目也能被我们攻克喵~！加油呐！(๑•̀ㅂ•́)و✧