Overview

For each interval, if we know “given an initial HP \(d\), what is the remaining HP after traversing the interval and how many monsters were defeated,” then query 2 l r d can be processed efficiently.
Taking advantage of the small constraint \(C \le 50\), we store a transition table for each HP value at every segment tree node, enabling fast both updates and range queries.

Analysis

The tricky aspect of this problem is that query 2 is not a simple sum or minimum — it is a state-dependent operation where the result depends on the current HP.

For example, for a single monster (with strength \(a\)), given initial HP \(d\):

• If \(d \ge a\), it can be defeated (kill count +1, HP becomes \(d-a\))
• If \(d < a\), it cannot be defeated (kill count +0, HP remains \(d\))

In other words, a single monster can be viewed as a function that takes HP \(d\) as input and returns “(next HP, kill count increment)”.

---

If we naively simulate 2 l r d each time, one query takes \(O(r-l+1)\), which is \(O(N)\) in the worst case.
Doing this \(Q\) times results in \(O(NQ)\) in the worst case, which is too slow for \(N=50000, Q=20000\).

---

The key observation here is:

• HP only takes \(C+1\) possible values in \(0..C\) (and \(C \le 50\))
• An entire interval can also have a “transition table indexed by initial HP”
• The transition tables of two adjacent intervals can be composed

Let the left interval be \(L\) and the right interval be \(R\). For initial HP \(d\):

1. First pass through the left → intermediate HP \(m = L.rem[d]\), kill count \(L.cnt[d]\)
2. Then pass through the right → final HP \(R.rem[m]\), kill count \(R.cnt[m]\)

Therefore, the parent interval has: - rem[d] = R.rem[L.rem[d]] - cnt[d] = L.cnt[d] + R.cnt[L.rem[d]]

Since this “function composition” is possible, it is extremely compatible with segment trees.

Algorithm

Each segment tree node stores the following (arrays of length \(C+1\)):

• rem[d]: the remaining HP after processing the interval with initial HP \(d\)
• cnt[d]: the number of monsters that can be defeated in the interval

1. Creating Leaf Nodes

For a single monster (with strength val), enumerate all \(d=0..C\): - If \(d \ge val\): rem[d]=d-val, cnt[d]=1 - Otherwise: rem[d]=d, cnt[d]=0

2. Merging Nodes

Create parent P from left and right nodes L, R: - mid = L.rem[d] - P.rem[d] = R.rem[mid] - P.cnt[d] = L.cnt[d] + R.cnt[mid]

This is done for all \(d=0..C\).

3. Update Query 1 p x

Rebuild the leaf at position p with the new strength x, then recompute by merging on the way back up.
This is processed in proportion to the height of the segment tree.

4. Retrieval Query 2 l r d

Recurse similarly to a standard range query, while composing in the correct order — passing the remaining HP from the left result to the right.

The query function returns {remaining HP, kill count}: - Out of range returns the identity transformation {hp, 0} - Full coverage directly looks up the node’s table {rem[hp], cnt[hp]} - Partial coverage processes left then right in order and composes

This yields the correct kill count.

Complexity

• Time complexity:
  
  • Construction: \(O(NC)\)
    
  • Per update: \(O(C \log N)\)
    
  • Per query: \(O(\log N)\) node visits, each with \(O(1)\) lookup (only recursive composition), so effectively \(O(\log N)\)
    (However, merging during construction and updates costs \(O(C)\))
• Space complexity: \(O(NC)\) (each node holds two arrays of length \(C+1\))

Implementation Notes

• The essence of this approach is “representing an interval as an HP transition function.”

• In query, the order is critical: process the left interval first, then pass the remaining HP to the right (reversing the order leads to wrong answers).

• Since the range of rem values is \(0..C\), memory is saved by using unsigned char (safe because \(C \le 50\)).

• Returning {hp, 0} (identity transformation) for out-of-range cases allows the recursive composition to be written cleanly.

  Source Code

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

struct Node {
    // For each initial hp d (0..C):
    // rem[d] = hp after processing this segment
    // cnt[d] = number of monsters defeated in this segment
    vector<unsigned char> rem; // values 0..C
    vector<int> cnt;
};

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

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

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

    int SZ = C + 1;
    vector<Node> seg(4 * N + 5);

    auto make_leaf = [&](int val) {
        Node nd;
        nd.rem.resize(SZ);
        nd.cnt.resize(SZ);
        for (int d = 0; d <= C; d++) {
            if (d >= val) {
                nd.rem[d] = (unsigned char)(d - val);
                nd.cnt[d] = 1;
            } else {
                nd.rem[d] = (unsigned char)d;
                nd.cnt[d] = 0;
            }
        }
        return nd;
    };

    function<Node(const Node&, const Node&)> merge_node = [&](const Node& L, const Node& R) {
        Node P;
        P.rem.resize(SZ);
        P.cnt.resize(SZ);
        for (int d = 0; d <= C; d++) {
            int mid = L.rem[d];
            P.rem[d] = R.rem[mid];
            P.cnt[d] = L.cnt[d] + R.cnt[mid];
        }
        return P;
    };

    function<void(int,int,int)> build = [&](int idx, int l, int r) {
        if (l == r) {
            seg[idx] = make_leaf(A[l]);
            return;
        }
        int m = (l + r) >> 1;
        build(idx << 1, l, m);
        build(idx << 1 | 1, m + 1, r);
        seg[idx] = merge_node(seg[idx << 1], seg[idx << 1 | 1]);
    };

    function<void(int,int,int,int,int)> update = [&](int idx, int l, int r, int pos, int val) {
        if (l == r) {
            seg[idx] = make_leaf(val);
            return;
        }
        int m = (l + r) >> 1;
        if (pos <= m) update(idx << 1, l, m, pos, val);
        else update(idx << 1 | 1, m + 1, r, pos, val);
        seg[idx] = merge_node(seg[idx << 1], seg[idx << 1 | 1]);
    };

    function<pair<int,int>(int,int,int,int,int,int)> query = [&](int idx, int l, int r, int ql, int qr, int hp) -> pair<int,int> {
        if (qr < l || r < ql) return {hp, 0};
        if (ql <= l && r <= qr) {
            return {seg[idx].rem[hp], seg[idx].cnt[hp]};
        }
        int m = (l + r) >> 1;
        auto leftRes = query(idx << 1, l, m, ql, qr, hp);
        auto rightRes = query(idx << 1 | 1, m + 1, r, ql, qr, leftRes.first);
        return {rightRes.first, leftRes.second + rightRes.second};
    };

    build(1, 1, N);

    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, x;
            cin >> p >> x;
            update(1, 1, N, p, x);
        } else {
            int l, r, d;
            cin >> l >> r >> d;
            auto ans = query(1, 1, N, l, r, d);
            cout << ans.second << '\n';
        }
    }

    return 0;
}

---

This editorial was generated by gpt-5.3-codex.