Overview

We want to find how many monsters can be defeated when processing monsters in the interval \([l,r]\) from left to right, starting with initial health \(d\).
Since there are point updates, we manage the “results per health value” for each interval using a segment tree.

Observation

Health and monster strength values are all between \(0\) and \(C\), and \(C \leq 50\), which is very small.

The key insight is that for a given interval, we can precompute for every \(h = 0, 1, \dots, C\):

When the initial health is \(h\), how much health remains at the end, and how many monsters can be defeated?

For example, we store the following arrays as information representing an interval:

• rem[h]: Remaining health after processing this interval with initial health \(h\)
• cnt[h]: Number of monsters defeated when processing this interval with initial health \(h\)

If we have this information, the answer to query 2 l r d is simply cnt[d] for that interval.

---

Naively simulating from \(l\) to \(r\) for each query takes \(O(NQ)\) in the worst case.
With \(N \leq 50000\) and \(Q \leq 20000\), this is too slow.

Therefore, we manage interval information using a segment tree.

When splitting an interval into left and right halves, we process the left interval first and then the right interval, so interval information can be composed.

Let \(L\) be the left interval and \(R\) be the right interval.
When the initial health is \(h\):

1. Process the left interval

   • Remaining health is L.rem[h]
   • Number defeated is L.cnt[h]

2. Process the right interval with the remaining health

   • Remaining health is R.rem[L.rem[h]]
   • Additional defeats are R.cnt[L.rem[h]]

Therefore, for the merged interval:

\[ \text{rem}[h] = R.\text{rem}[L.\text{rem}[h]] \]

\[ \text{cnt}[h] = L.\text{cnt}[h] + R.\text{cnt}[L.\text{rem}[h]] \]

By storing arrays of length \(C+1\) at each node, we can efficiently handle point updates and range queries.

Algorithm

1. Node Representing a Single Monster

Consider a single monster with strength \(a\).

For initial health \(h\):

• If \(h \geq a\), the monster can be defeated
  
  • Remaining health is \(h - a\)
  • Number defeated is \(1\)
• If \(h < a\), the monster cannot be defeated
  
  • Remaining health is \(h\)
  • Number defeated is \(0\)

Thus, a leaf node is constructed as follows:

\[ \text{rem}[h] = \begin{cases} h-a & (h \geq a) \\ h & (h < a) \end{cases} \]

\[ \text{cnt}[h] = \begin{cases} 1 & (h \geq a) \\ 0 & (h < a) \end{cases} \]

In particular, when \(a = 0\), the monster can be defeated at any health, and health does not decrease.

---

2. Identity Element for Empty Intervals

For range queries on the segment tree, we need a node representing an empty interval.

In an empty interval, nothing happens, so:

\[ \text{rem}[h] = h \]

\[ \text{cnt}[h] = 0 \]

We use this as the identity element.

---

3. Merging Nodes

Given the left interval L and the right interval R, the merge result res is computed as follows:

for (int h = 0; h <= C; h++) {
    int mid = L.rem[h];
    res.rem[h] = R.rem[mid];
    res.cnt[h] = L.cnt[h] + R.cnt[mid];
}

This means “process the left interval first, then process the right interval with the remaining health.”

---

4. Point Update

Operation 1 p x changes the strength of the \(p\)-th monster to \(x\).

1. Rebuild the corresponding leaf node as a node with strength \(x\)
2. Recompute parent nodes upward

Since this is a segment tree, the number of nodes that need updating is \(O(\log N)\).
Recomputing each node takes \(O(C)\), so the total cost of a point update is \(O(C \log N)\).

---

5. Range Query

Operation 2 l r d computes the node information for the interval \([l,r]\) and outputs cnt[d].

In a segment tree, a range is decomposed into multiple nodes for retrieval.

However, in this problem, the order of merging matters.
Since we need to process from left to right, we maintain:

• Results collected from the left side: left_res
• Results collected from the right side: right_res

separately.

Finally:

ans = merge_node(left_res, right_res);

gives us the information for the entire interval.

The answer is then:

ans.cnt[d]

Complexity

• Time complexity:
  • Construction: \(O(NC)\)
  • One update: \(O(C \log N)\)
  • One query: \(O(C \log N)\)
  • Overall: \(O(NC + QC \log N)\)
• Space complexity: \(O(NC)\)

Since \(C \leq 50\), iterating over all values from \(0\) to \(C\) at each node is sufficiently fast.

Implementation Notes

• Each Node holds two arrays: rem and cnt.

• The identity element for empty intervals sets rem[h] = h and cnt[h] = 0.

• Merging is performed in the order “process the left first, then process the right.”

• In range queries, left_res and right_res are managed separately to preserve the correct merge order.

• The input is \(1\)-indexed, but the implementation converts to \(0\)-indexed internally.

  Source Code

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

struct Node {
    vector<int> rem;
    vector<int> cnt;

    Node() {}
    Node(int C, bool identity) : rem(C + 1), cnt(C + 1, 0) {
        for (int h = 0; h <= C; h++) rem[h] = h;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, C, Q;
    cin >> N >> C >> Q;

    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    int size = 1;
    while (size < N) size <<= 1;

    auto identity = [&]() -> Node {
        return Node(C, true);
    };

    auto make_leaf = [&](int a) -> Node {
        Node res(C, true);
        for (int h = 0; h <= C; h++) {
            if (h >= a) {
                res.rem[h] = h - a;
                res.cnt[h] = 1;
            } else {
                res.rem[h] = h;
                res.cnt[h] = 0;
            }
        }
        return res;
    };

    auto merge_node = [&](const Node& L, const Node& R) -> Node {
        Node res(C, true);
        for (int h = 0; h <= C; h++) {
            int mid = L.rem[h];
            res.rem[h] = R.rem[mid];
            res.cnt[h] = L.cnt[h] + R.cnt[mid];
        }
        return res;
    };

    vector<Node> seg(2 * size, identity());

    for (int i = 0; i < N; i++) {
        seg[size + i] = make_leaf(A[i]);
    }
    for (int i = size - 1; i >= 1; i--) {
        seg[i] = merge_node(seg[i << 1], seg[i << 1 | 1]);
    }

    while (Q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int p, x;
            cin >> p >> x;
            --p;

            int idx = size + p;
            seg[idx] = make_leaf(x);
            idx >>= 1;

            while (idx >= 1) {
                seg[idx] = merge_node(seg[idx << 1], seg[idx << 1 | 1]);
                idx >>= 1;
            }
        } else {
            int l, r, d;
            cin >> l >> r >> d;
            --l;

            Node left_res = identity();
            Node right_res = identity();

            int L = size + l;
            int R = size + r;

            while (L < R) {
                if (L & 1) {
                    left_res = merge_node(left_res, seg[L]);
                    L++;
                }
                if (R & 1) {
                    --R;
                    right_res = merge_node(seg[R], right_res);
                }
                L >>= 1;
                R >>= 1;
            }

            Node ans = merge_node(left_res, right_res);
            cout << ans.cnt[d] << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.