Overview

This problem involves a row of monsters, where you must handle “strength updates” and “simulations of how many monsters can be defeated in a specific interval.” By leveraging the fact that the maximum health \(C\) is very small at \(50\), we can efficiently solve this by storing results for each possible health value in a segment tree.

Analysis

1. Limitations of Naive Simulation

For a query 2 l r d, if we naively compute from the \(l\)-th to the \(r\)-th monster each time, a single query takes up to \(O(N)\). Since there are \(Q\) queries, the total time complexity becomes \(O(NQ)\), which does not fit within the time limit for the given constraints (\(N=50,000, Q=20,000\)).

2. Exploiting the Small Upper Bound \(C\) on Health

The key feature of this problem is that the maximum value \(C\) for monster strength and health is very small at \(50\). For a contiguous interval of monsters, the information “if you enter this interval with health \(h\), what is your final health and how many monsters can you defeat?” can be precomputed for all \(h \in [0, C]\).

3. Using a Segment Tree

Since we need to “merge interval information,” a segment tree is a natural choice. Each node of the segment tree stores the following information as arrays:

• next_h[h]: The remaining health after passing through this interval when entering with health \(h\)
• count[h]: The total number of monsters defeated in this interval when entering with health \(h\)

When merging two nodes (left child \(L\) and right child \(R\)), the procedure is as follows: 1. Enter the left interval with health \(h\). 2. After passing through the left interval, the health becomes \(mid\_h = L.next\_h[h]\), and the number defeated is \(L.count[h]\). 3. Next, enter the right interval with health \(mid\_h\). 4. After passing through the right interval, the health becomes \(R.next\_h[mid\_h]\), and the additional number defeated is \(R.count[mid\_h]\).

By computing this for all \(h\), the parent node’s information can be constructed in \(O(C)\).

Algorithm

1. Segment Tree Construction:
   • Leaf node (monster \(i\)): For health \(h\), if \(h \geq A_i\), set next_h = h - A_i, count = 1; otherwise, set next_h = h, count = 0.
   • Internal nodes: Merge the left and right children according to the merge rules described above.
2. Point Update (Query 1):
   • Update the leaf node of the specified monster and recompute upward toward the root in \(O(C \log N)\).
3. Range Query (Query 2):
   • Extract the \(O(\log N)\) nodes that cover the range \([l, r]\).
   • Using the initial health \(d\), traverse the extracted nodes from left to right, updating the current health while accumulating the total number of defeated monsters.

Complexity

• Time Complexity: \(O((N + Q \log N) \cdot C)\)
  • Segment tree construction: \(O(NC)\)
  • Each update: \(O(C \log N)\)
  • Each query: \(O(\log N)\) (while node merging would cost \(O(C \log N)\), since we only need to trace a single value of \(d\), it is \(O(\log N)\))
• Space Complexity: \(O(N \cdot C)\)
  • Because each node of the segment tree holds two arrays of size \(C\).

Implementation Tips

• Memory Management: Since \(C\) is small, using a compact data type such as signed char for the next_h array can save memory usage.

• Query Processing: The key technique is to list the nodes corresponding to the range \([l, r]\) and, when processing them in order, always carry over the “current health” to look up the next node’s count and next_h.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

/**
 * Problem Analysis:
 * The problem involves updating monster strengths and querying the number of monsters defeated
 * given a starting health and a range of monsters. The constraints are N <= 50,000, C <= 50,
 * and Q <= 20,000. The small value of C (monster strength and health upper bound) is the key.
 *
 * Approach:
 * We can use a Segment Tree where each node stores the result of processing the monsters in
 * its range for every possible initial health from 0 to C.
 * For each node and each initial health h (0 <= h <= C), we store:
 * 1. next_h: The health remaining after processing all monsters in the range.
 * 2. count: The total number of monsters defeated in the range.
 *
 * Complexity:
 * - Build: O(N * C)
 * - Update: O(C * log N)
 * - Query: O(log N) - since we only need the result for one initial health value.
 * Total complexity: O(NC + Q * C * log N), which fits well within the 2-second limit.
 */

const int MAXC = 51;

struct Node {
    // next_h stores the resulting health (0 to 50), so signed char is sufficient.
    signed char next_h[MAXC];
    // count stores the number of defeated monsters, which can be up to N (50,000).
    int count[MAXC];
};

// Segment Tree array. Size 2^17 is enough for N = 50,000.
Node tree[1 << 17];
int N, C, Q;
int leaf_offset;

// Function to initialize a leaf node based on monster strength val.
void make_leaf(int idx, int val) {
    for (int h = 0; h <= C; ++h) {
        if (h >= val) {
            tree[idx].next_h[h] = (signed char)(h - val);
            tree[idx].count[h] = 1;
        } else {
            tree[idx].next_h[h] = (signed char)h;
            tree[idx].count[h] = 0;
        }
    }
}

// Function to merge two children nodes into their parent.
void merge_nodes(int idx) {
    int L = 2 * idx;
    int R = 2 * idx + 1;
    for (int h = 0; h <= C; ++h) {
        int mid_h = (int)tree[L].next_h[h];
        tree[idx].next_h[h] = tree[R].next_h[mid_h];
        tree[idx].count[h] = tree[L].count[h] + tree[R].count[mid_h];
    }
}

int main() {
    // Optimize standard I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> C >> Q)) return 0;

    // Determine the leaf offset for the segment tree.
    leaf_offset = 1;
    while (leaf_offset < N) leaf_offset <<= 1;

    // Initialize leaves for actual monsters.
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        make_leaf(leaf_offset + i, a);
    }
    // Initialize dummy leaves (monsters that don't exist/affect anything).
    for (int i = N; i < leaf_offset; ++i) {
        for (int h = 0; h <= C; ++h) {
            tree[leaf_offset + i].next_h[h] = (signed char)h;
            tree[leaf_offset + i].count[h] = 0;
        }
    }

    // Build the segment tree by merging nodes bottom-up.
    for (int i = leaf_offset - 1; i >= 1; --i) {
        merge_nodes(i);
    }

    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            // Update monster strength.
            int p, x;
            cin >> p >> x;
            int idx = p - 1 + leaf_offset;
            make_leaf(idx, x);
            while (idx > 1) {
                idx >>= 1;
                merge_nodes(idx);
            }
        } else {
            // Query number of defeated monsters in range [l, r] with initial health d.
            int l, r, d;
            cin >> l >> r >> d;
            int l_idx = l + leaf_offset - 1;
            int r_idx = r + leaf_offset - 1;

            // Collect segment tree nodes covering the range [l, r].
            static int left_nodes[64], right_nodes[64];
            int left_cnt = 0, right_cnt = 0;
            while (l_idx <= r_idx) {
                if (l_idx % 2 == 1) left_nodes[left_cnt++] = l_idx++;
                if (r_idx % 2 == 0) right_nodes[right_cnt++] = r_idx--;
                l_idx >>= 1;
                r_idx >>= 1;
            }

            // Process the collected nodes in sequence from left to right.
            int current_h = d;
            int total_defeated = 0;
            for (int i = 0; i < left_cnt; ++i) {
                int node = left_nodes[i];
                total_defeated += tree[node].count[current_h];
                current_h = (int)tree[node].next_h[current_h];
            }
            for (int i = right_cnt - 1; i >= 0; --i) {
                int node = right_nodes[i];
                total_defeated += tree[node].count[current_h];
                current_h = (int)tree[node].next_h[current_h];
            }
            cout << total_defeated << "\n";
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.