Overview

This is a problem about dungeon exploration where you clear rooms arranged in a line one by one, and you need to efficiently handle room information updates and exploration queries. We solve it efficiently by using a segment tree to manage the minimum combat power required to clear each interval.

Analysis

Issues with the Naive Approach

If we simulate from room \(1\) sequentially for each query 2, it takes \(O(N)\) in the worst case, and combined with the number of queries, this results in \(O(NQ)\) which causes TLE.

Key Insight

Whether you can clear all rooms in an interval \([l, r]\) can be determined solely by the combat power \(s\) at the time of entry. Specifically, if the combat power before entering the interval is large enough, all rooms in that interval can be cleared.

We define \(\mathrm{min\_need}(l, r)\) as the minimum initial combat power required to clear the interval \([l, r]\).

Merging Intervals

To compute \(\mathrm{min\_need}\) for the entire interval \([l, r]\) from the left half \([l, m]\) and the right half \([m+1, r]\):

• To clear the left half: initial combat power \(\geq \mathrm{min\_need}(l, m)\)
• To clear the right half: the combat power after clearing the left half must be \(\geq \mathrm{min\_need}(m+1, r)\). Since the combat power increases by a total of \(\mathrm{sum\_b}(l, m)\) in the left half, the initial combat power must be \(\geq \mathrm{min\_need}(m+1, r) - \mathrm{sum\_b}(l, m)\)

Therefore:

\[\mathrm{min\_need}(l, r) = \max\bigl(\mathrm{min\_need}(l, m),\; \mathrm{min\_need}(m+1, r) - \mathrm{sum\_b}(l, m)\bigr)\]

Algorithm

Build a segment tree where each node stores the following:

• min_need: the minimum initial combat power required to clear all rooms in the interval
• sum_b: the total combat power increase from defeating all monsters in the interval

Update (Query 1): Update the corresponding leaf and recompute its ancestors. \(O(\log N)\).

Exploration (Query 2): Descend on the segment tree as follows:

1. If the entire interval of the current node can be cleared (\(s \geq \mathrm{min\_need}\)), add sum_b to \(s\) and return the length of the interval.
2. Otherwise, first recurse into the left child.
3. Only if the left child is fully cleared, also recurse into the right child.
4. If the exploration fails partway through the left child, return the count up to that point.

This descent allows us to determine “how far we can progress” in \(O(\log N)\).

Concrete Example

If the rooms have \([A_1=3, A_2=5, A_3=8]\) and \([B_1=2, B_2=1, B_3=4]\):

• Starting with combat power \(s=4\): room 1 can be cleared (\(4 \geq 3\), \(s=6\)), room 2 can also be cleared (\(6 \geq 5\), \(s=7\)), room 3 cannot be cleared (\(7 < 8\)) → the answer is 2.
• The min_need at the root of the segment tree is \(\max(3, \max(5, 8-1) - 2) = \max(3, 5) = 5\), so if \(s \geq 5\), all rooms are cleared.

Complexity

• Time complexity: \(O(N + Q \log N)\) (construction \(O(N)\), each query \(O(\log N)\))
• Space complexity: \(O(N)\) (size of the segment tree)

Implementation Notes

• Since subtraction in the min_need calculation can become negative, use long long type.

• During query descent, update the combat power \(s\) by passing it by reference, so that the \(s\) after clearing the left child can be directly used for the right child’s evaluation.

• At leaf nodes, store the information of a single room directly: min_need = A[i], sum_b = B[i].

  Source Code

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

struct Node {
    long long min_need;
    long long sum_b;
};

const int MAXN = 200005;
Node tree[4 * MAXN];
int A[MAXN], B[MAXN];
int N, Q;

void build(int v, int l, int r) {
    if (l == r) {
        tree[v].min_need = A[l];
        tree[v].sum_b = B[l];
        return;
    }
    int m = (l + r) / 2;
    build(2*v, l, m);
    build(2*v+1, m+1, r);
    tree[v].sum_b = tree[2*v].sum_b + tree[2*v+1].sum_b;
    tree[v].min_need = max(tree[2*v].min_need, tree[2*v+1].min_need - tree[2*v].sum_b);
}

void update(int v, int l, int r, int pos) {
    if (l == r) {
        tree[v].min_need = A[l];
        tree[v].sum_b = B[l];
        return;
    }
    int m = (l + r) / 2;
    if (pos <= m) update(2*v, l, m, pos);
    else update(2*v+1, m+1, r, pos);
    tree[v].sum_b = tree[2*v].sum_b + tree[2*v+1].sum_b;
    tree[v].min_need = max(tree[2*v].min_need, tree[2*v+1].min_need - tree[2*v].sum_b);
}

int query(int v, int l, int r, long long &s) {
    if (l == r) {
        if (s >= tree[v].min_need) {
            s += tree[v].sum_b;
            return 1;
        }
        return 0;
    }
    if (s >= tree[v].min_need) {
        s += tree[v].sum_b;
        return r - l + 1;
    }
    int m = (l + r) / 2;
    int left_count = query(2*v, l, m, s);
    if (left_count < m - l + 1) {
        return left_count;
    }
    return left_count + query(2*v+1, m+1, r, s);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> Q;
    for (int i = 1; i <= N; i++) {
        cin >> A[i] >> B[i];
    }
    build(1, 1, N);
    
    for (int q = 0; q < Q; q++) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, a, b;
            cin >> i >> a >> b;
            A[i] = a;
            B[i] = b;
            update(1, 1, N, i);
        } else {
            long long s;
            cin >> s;
            cout << query(1, 1, N, s) << "\n";
        }
    }
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.