电脑配件 - 题解

标签与难度

标签: 数据结构, 线段树, 二分查找, 离线处理, 区间修改, 区间查询, 懒标记难度: 2100

题目大意喵~

主人 sama，你好呀！这道题目是说，我们有 n 种电脑资源，每种资源初始有一定数量 a_i 的说。然后呢，小蓝会提出 m 个请求，每个请求都是需要 l_i 到 r_i 范围内的所有资源各 c_i 份。

我们得按顺序处理这些请求。如果在处理第 k 个请求时，有任何一种资源的存量不够了，电脑就会“卡死”，我们就记录下这个卡死的请求编号 k。如果所有请求都能满足，那就不会卡死啦。

现在小蓝想买 q 种配件中的一种。每种配件都能给一个特定区间 [ql, qr] 内的所有资源增加 x 份。我们的任务是，对于每一种配件，都要独立计算出：如果从一开始就装上这个配件，小蓝的请求会在第几次卡死呢？如果永远不会卡死，就输出 -1 呐。

简单来说，就是 q 次独立的询问，每次询问为一个“增强版”的初始资源状态，计算在该状态下首次发生资源不足的请求是第几个，喵~

解题思路分析

这道题看起来有点复杂，因为它有多次询问，而且每次询问都会改变初始条件。如果每次询问都从头模拟一遍，那肯定会超时的说！( TωT )

所以，我们需要一种更聪明的办法，喵~ 这种“多次询问，每次询问都基于一个初始状态”的模式，通常可以考虑离线处理和预计算。

核心思路：预计算 + 二分查找

我们可以先不考虑配件的加成，完整地模拟一遍 m 次请求的过程。在每次请求后，我们记录下系统的“危机状态”。然后，对于每个配件的询问，我们利用这些预计算好的信息，通过二分查找快速找到答案！

第一步：预计算危机信息

我们来模拟一下没有配件时的情况。资源的变化是“区间减法”，而判断是否卡死是“查询全局最小值是否小于0”。这简直是为线段树量身定做的场景，喵！

我们可以建一棵线段树，维护 n 种资源的数量。线段树的每个节点需要保存它所代表的区间的最小值。

初始化: 用初始的 a_i 数组建树。
模拟请求: 我们从第 1 个请求到第 m 个请求，依次处理：
- 对于第 i 个请求 (l_i, r_i, c_i)，我们在线段树上对区间 [l_i, r_i] 进行一次区间减法，都减去 c_i。这可以用懒标记（lazy propagation）高效实现，喵~
- 更新后，我们查询整个 [1, n] 区间的最小值。
- 如果最小值小于 0，说明在第 i 次请求后，系统出现了资源不足的“危机”！
- 这时，我们需要记录下这次危机的详细信息：
  - 最少需要多少额外资源才能渡过难关？ 这就是最小值的绝对值，我们记为 needed_i = -min_val。
  - 是哪些资源出现了短缺？ 我们需要找到出现这个最小值的最左边和最右边的资源编号，记为 left_bound_i 和 right_bound_i。这个可以通过在线段树上进行特殊的查找（类似二分）来高效完成。

我们用一个数组 crisis_reports 来保存每一轮请求后的危机信息。crisis_reports[i] 就存放第 i 次请求后的 {needed_i, left_bound_i, right_bound_i}。如果第 i 次请求后没有危机（全局最小值大于等于0），我们就存一个特殊标记，比如 needed_i = 0。

第二步：回答询问

预计算完成后，我们手上就有了一份完整的“危机报告”。现在对于每个配件 (ql, qr, x) 的询问，我们要找的是第一个无法被这个配件拯救的危机。

一个请求 k 会卡死，当且仅当：

在第 k 步确实发生了危机（即 crisis_reports[k].needed > 0）。
并且，当前配件无法完全覆盖这次危机。

配件无法覆盖危机，有两种情况：

配件增加资源的范围 [ql, qr] 没有完全包含发生危机的资源范围 [left_bound_k, right_bound_k]。也就是说，ql > left_bound_k 或者 qr < right_bound_k。
配件增加的资源量 x 不足以弥补亏空，即 x < needed_k。

所以，一个请求 k 能被配件 (ql, qr, x) 拯救的条件是： crisis_reports[k].needed == 0 或者 (ql <= left_bound_k 且 qr >= right_bound_k 且 x >= needed_k)。

注意到一个很重要的性质：如果第 k 个请求能被拯救，那么所有 j < k 的请求也一定能被拯救（因为资源亏空是随请求数增加而只可能变多或不变的）。这个单调性告诉我们，可以用二分查找来寻找答案！

对于每个配件查询，我们在 [1, m] 的请求编号上进行二分查找，寻找第一个不能被拯救的请求 k。

我们猜一个中间的请求号 mid。
用上面的条件检查 mid 能否被拯救。
如果能被拯救，说明真正的卡死点在 mid 之后，我们就在 [mid + 1, m] 这个范围里继续找。
如果不能被拯救，说明卡死点可能就是 mid，或者还在更前面，我们就在 [1, mid] 这个范围里找。

这样，每次查询只需要 $O(\log m)$ 的时间，非常快！

总结一下整个流程，喵~

预处理阶段 ( $O(m \log n)$ ):
- 用线段树模拟 m 次请求。
- 每次请求后，进行一次区间更新 ( $O(\log n)$ ) 和三次查询（全局最小，最左危机点，最右危机点，都是 $O(\log n)$ ）。
- 记录下每次请求后的危机信息。
查询阶段 ( $O(q \log m)$ ):
- 对 q 个配件，每个都用二分查找答案。
- 二分查找的 check 函数是 $O(1)$ 的。

这样就能愉快地解决问题啦，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，加了详细的注释，希望能帮到主人 sama 呐！

cpp

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

using namespace std;

const long long INF = 1e18; // 用一个很大的数表示无穷大

// 存储危机信息的数据结构
struct CrisisInfo {
    long long needed; // 需要的最小额外资源量
    int l_idx;      // 发生危机的最左侧资源编号
    int r_idx;      // 发生危机的最右侧资源编号
};

// 线段树节点
struct Node {
    long long min_val; // 区间最小值
    long long lazy_add; // 懒标记
};

vector<Node> tree;
vector<long long> initial_resources;
int n_resources;

// --- 线段树核心功能 ---

// 将懒标记下推
void push_down(int u) {
    if (tree[u].lazy_add != 0) {
        // 左右子节点ID
        int left_child = u * 2;
        int right_child = u * 2 + 1;

        // 更新子节点的最小值
        tree[left_child].min_val += tree[u].lazy_add;
        tree[right_child].min_val += tree[u].lazy_add;

        // 传递懒标记
        tree[left_child].lazy_add += tree[u].lazy_add;
        tree[right_child].lazy_add += tree[u].lazy_add;

        // 清除当前节点的懒标记
        tree[u].lazy_add = 0;
    }
}

// 由子节点信息更新父节点
void push_up(int u) {
    tree[u].min_val = min(tree[u * 2].min_val, tree[u * 2 + 1].min_val);
}

// 建树
void build(int u, int l, int r) {
    tree[u].lazy_add = 0;
    if (l == r) {
        tree[u].min_val = initial_resources[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    push_up(u);
}

// 区间更新
void update(int u, int l, int r, int update_l, int update_r, long long val) {
    if (update_l > update_r) return;
    if (l >= update_l && r <= update_r) {
        tree[u].min_val += val;
        tree[u].lazy_add += val;
        return;
    }
    push_down(u);
    int mid = l + (r - l) / 2;
    if (update_l <= mid) {
        update(u * 2, l, mid, update_l, update_r, val);
    }
    if (update_r > mid) {
        update(u * 2 + 1, mid + 1, r, update_l, update_r, val);
    }
    push_up(u);
}

// 查询区间最小值
long long query_min(int u, int l, int r, int query_l, int query_r) {
    if (query_l > query_r) return INF;
    if (l >= query_l && r <= query_r) {
        return tree[u].min_val;
    }
    push_down(u);
    int mid = l + (r - l) / 2;
    long long min_val = INF;
    if (query_l <= mid) {
        min_val = min(min_val, query_min(u * 2, l, mid, query_l, query_r));
    }
    if (query_r > mid) {
        min_val = min(min_val, query_min(u * 2 + 1, mid + 1, r, query_l, query_r));
    }
    return min_val;
}

// 在线段树上二分查找第一个值小于0的下标
int find_first_negative(int u, int l, int r) {
    if (tree[u].min_val >= 0) return -1; //整个区间都安全
    if (l == r) return l; // 找到了叶子节点
    
    push_down(u);
    int mid = l + (r - l) / 2;
    if (tree[u * 2].min_val < 0) {
        return find_first_negative(u * 2, l, mid);
    }
    return find_first_negative(u * 2 + 1, mid + 1, r);
}

// 在线段树上二分查找最后一个值小于0的下标
int find_last_negative(int u, int l, int r) {
    if (tree[u].min_val >= 0) return -1;
    if (l == r) return l;
    
    push_down(u);
    int mid = l + (r - l) / 2;
    if (tree[u * 2 + 1].min_val < 0) {
        return find_last_negative(u * 2 + 1, mid + 1, r);
    }
    return find_last_negative(u * 2, l, mid);
}


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

    int m, q;
    cin >> n_resources >> m >> q;

    initial_resources.resize(n_resources + 1);
    for (int i = 1; i <= n_resources; ++i) {
        cin >> initial_resources[i];
    }

    tree.resize(n_resources * 4 + 5);
    build(1, 1, n_resources);

    vector<CrisisInfo> crisis_reports(m + 1);

    // --- 预计算阶段 ---
    for (int i = 1; i <= m; ++i) {
        int l, r;
        long long c;
        cin >> l >> r >> c;
        
        update(1, 1, n_resources, l, r, -c);

        long long current_min = query_min(1, 1, n_resources, 1, n_resources);

        if (current_min < 0) {
            crisis_reports[i].needed = -current_min;
            crisis_reports[i].l_idx = find_first_negative(1, 1, n_resources);
            crisis_reports[i].r_idx = find_last_negative(1, 1, n_resources);
        } else {
            crisis_reports[i] = {0, -1, -1}; // 无危机
        }
    }

    // --- 查询阶段 ---
    for (int i = 0; i < q; ++i) {
        int ql, qr;
        long long x;
        cin >> ql >> qr >> x;

        int low = 1, high = m, ans = m + 1;
        
        // 二分查找第一个无法被拯救的请求
        while (low <= high) {
            int mid = low + (high - low) / 2;
            const auto& crisis = crisis_reports[mid];

            bool can_survive = false;
            if (crisis.needed == 0) { // 本来就没危机
                can_survive = true;
            } else {
                // 配件能完全覆盖危机范围，并且提供足够资源
                if (ql <= crisis.l_idx && qr >= crisis.r_idx && x >= crisis.needed) {
                    can_survive = true;
                }
            }

            if (can_survive) {
                low = mid + 1; // 尝试更晚的请求
            } else {
                ans = mid;     // 这可能是答案，但要尝试更早的
                high = mid - 1;
            }
        }

        if (ans > m) {
            cout << -1 << "\n";
        } else {
            cout << ans << "\n";
        }
    }

    return 0;
}

复杂度分析

时间复杂度: $O(m \log n + q \log m)$
- 预计算阶段: 我们要处理 m 个请求。对于每个请求，我们需要在线段树上做一次区间更新 ( $O(\log n)$ )、一次全局最小值查询 ( $O(\log n)$ )、一次最左负数查询 ( $O(\log n)$ ) 和一次最右负数查询 ( $O(\log n)$ )。所以预计算的总时间是 $O(m \log n)$ 。
- 查询阶段: 我们有 q 个配件查询。对于每个查询，我们使用二分查找，范围是 [1, m]，所以是 $O(\log m)$ 。检查函数 check 的复杂度是 $O(1)$ 。所以查询的总时间是 $O(q \log m)$ 。
- 两部分加起来就是 $O(m \log n + q \log m)$ 啦，喵~
空间复杂度: $O(n + m)$
- 线段树需要 $O(4n)$ 的空间来存储节点，也就是 $O(n)$ 的说。
- 我们需要一个数组 crisis_reports 来存储 m 次请求后的危机信息，这需要 $O(m)$ 的空间。
- 所以总的空间复杂度是 $O(n + m)$ 。

知识点总结

这道题是一道很棒的复合型题目，融合了多种算法思想，喵~

线段树 (Segment Tree): 解决区间问题的强大工具！本题中用于高效地进行区间加减和区间最小值查询。
懒标记 (Lazy Propagation): 实现高效区间修改的关键。当一个修改操作覆盖了线段树的某个节点代表的整个区间时，我们不需要继续递归下去，而是给这个节点打上一个“懒标记”，等需要查询其子区间时再把标记传递下去。
离线处理 (Offline Processing): 当所有查询都可以在处理任何操作之前读入时，我们就可以对它们进行排序或预处理，以更优的方式回答。这里我们先处理完所有请求，记录下中间状态，再统一回答查询。
二分查找 (Binary Search): 当问题答案具有单调性时，二分查找是快速定位答案的神器！本题中，“一个请求能否被拯救”这个性质就具有单调性，是使用二分查找的完美信号。
在数据结构上查找: 除了常规的查询，我们还可以在线段树的结构上进行类似二分的查找，来定位满足特定条件的第一个或最后一个元素，这比在 [1, n] 上二分套用线段树查询（ $O(\log^2 n)$ ）要更高效（ $O(\log n)$ ）。

希望这篇题解能帮助主人 sama 理解这道题的精髓！继续加油哦，喵~ (ฅ'ω'ฅ)

电脑配件 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心思路：预计算 + 二分查找 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​