Overview

This problem requires efficiently processing “strength updates” and “interval simulations (counting the number of monsters defeated while consuming health)” on a sequence of monsters. By leveraging the fact that the health upper bound \(C\) is small (\(C \leq 50\)), we speed things up by storing a lookup table of “input health → output health and defeat count” at each node of a segment tree.

Analysis

Problems with the Naive Approach

If we directly simulate operation 2 one monster at a time from \(l\) to \(r\), each operation takes \(O(N)\), resulting in \(O(NQ)\) over \(Q\) operations. With \(N = 50000, Q = 20000\), this is roughly \(10^9\) in the worst case, risking TLE.

Key Observation: \(C\) is Small

Health only takes integer values between \(0\) and \(C\). This means that for a given interval of monsters, the function “if you enter with health \(d\), what health do you exit with and how many monsters do you defeat?” has only \(C+1\) possible input patterns for \(d = 0, 1, \dots, C\).

If we precompute this function as a table, we can compose the functions of two intervals. Entering the left interval with health \(d\) yields exit health \(h_1\), which then serves as the input to the right interval’s function.

Concrete Example of Composition

For example, with \(C = 5\), if the left interval’s function is \(f\) and the right interval’s function is \(g\):

• Enter the left interval with health \(d=5\) → exit health \(f(5) = 3\), defeat count \(c_1 = 2\)
• Enter the right interval with health \(3\) → exit health \(g(3) = 1\), defeat count \(c_2 = 1\)
• Overall: health \(5 \to 1\), defeat count \(= 2 + 1 = 3\)

Algorithm

We use a segment tree, where each node stores the following tables:

• out_hp[d]: the remaining health at the exit when entering the interval with health \(d\)
• out_cnt[d]: the number of monsters defeated when entering the interval with health \(d\)

Leaf Node Construction (Single Monster)

When the monster’s strength is \(a\):

\[ \text{out\_hp}[d] = \begin{cases} d - a & (d \geq a) \\ d & (d < a) \end{cases}, \quad \text{out\_cnt}[d] = \begin{cases} 1 & (d \geq a) \\ 0 & (d < a) \end{cases} \]

Node Merging (Left child \(L\) and right child \(R\) → Parent)

For each \(d = 0, 1, \dots, C\):

\[ h_1 = L.\text{out\_hp}[d] \]

\[ \text{parent.out\_hp}[d] = R.\text{out\_hp}[h_1] \]

\[ \text{parent.out\_cnt}[d] = L.\text{out\_cnt}[d] + R.\text{out\_cnt}[h_1] \]

Processing Operations

• Operation 1 (Update): Rebuild the target leaf, then re-merge ancestors in order from bottom to top.
• Operation 2 (Query): Visit the nodes corresponding to the interval \([l, r]\) on the segment tree from left to right, updating the current health and accumulating the defeat count. When the entire interval fits within a single node, we simply look up the table in \(O(1)\).

Complexity

• Time Complexity:

  • Construction: \(O(NC)\) (merging each node takes \(O(C)\), with \(O(N)\) nodes)
  • Single update: \(O(C \log N)\) (merging \(O(\log N)\) nodes from leaf to root)
  • Single query: \(O(\log N)\) (\(O(1)\) table lookup at each visited node)
  • Overall: \(O(NC + QC\log N)\)

• Space Complexity: \(O(NC)\) (two arrays of size \(C+1\) at each node of the segment tree)

With \(N = 50000, C = 50, Q = 20000\), updates require approximately \(50 \times 16 \times 20000 = 1.6 \times 10^7\) operations, which is sufficiently fast.

Implementation Notes

• Allocate the segment tree array with a size of about \(4N\) (in the code, 200001 is used).

• For queries, if the interval is completely contained within a node, return the table as-is. If it partially overlaps, recurse into the left and right children and compose the results. The crucial point here is passing the output health from the left result as the input health to the right.

• Since \(C\) is small, enumerating the table entries with simple loops is sufficient. There is no need for bit manipulation or other optimizations.

  Source Code

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

int N, C, Q;

struct Node {
    int out_hp[51];
    int out_cnt[51];
};

Node tree[200001];

void build_leaf(int pos, int a) {
    for (int d = 0; d <= C; d++) {
        if (d >= a) {
            tree[pos].out_hp[d] = d - a;
            tree[pos].out_cnt[d] = 1;
        } else {
            tree[pos].out_hp[d] = d;
            tree[pos].out_cnt[d] = 0;
        }
    }
}

void merge(int pos) {
    int le = pos * 2, ri = pos * 2 + 1;
    for (int d = 0; d <= C; d++) {
        int h1 = tree[le].out_hp[d];
        tree[pos].out_hp[d] = tree[ri].out_hp[h1];
        tree[pos].out_cnt[d] = tree[le].out_cnt[d] + tree[ri].out_cnt[h1];
    }
}

int A[50001];

void build(int pos, int l, int r) {
    if (l == r) {
        build_leaf(pos, A[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(pos * 2, l, mid);
    build(pos * 2 + 1, mid + 1, r);
    merge(pos);
}

void update(int pos, int l, int r, int idx, int val) {
    if (l == r) {
        build_leaf(pos, val);
        return;
    }
    int mid = (l + r) / 2;
    if (idx <= mid) update(pos * 2, l, mid, idx, val);
    else update(pos * 2 + 1, mid + 1, r, idx, val);
    merge(pos);
}

pair<int,int> query(int pos, int l, int r, int ql, int qr, int hp) {
    if (ql <= l && r <= qr) {
        return {tree[pos].out_hp[hp], tree[pos].out_cnt[hp]};
    }
    int mid = (l + r) / 2;
    pair<int,int> res = {hp, 0};
    if (ql <= mid) {
        res = query(pos * 2, l, mid, ql, qr, hp);
    }
    if (qr > mid) {
        auto [h2, c2] = query(pos * 2 + 1, mid + 1, r, ql, qr, res.first);
        res = {h2, res.second + c2};
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> C >> Q;
    for (int i = 1; i <= N; i++) cin >> A[i];
    
    build(1, 1, N);
    
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int p, x;
            cin >> p >> x;
            update(1, 1, N, p, x);
        } else {
            int l, r, d;
            cin >> l >> r >> d;
            auto [hp, cnt] = query(1, 1, N, l, r, d);
            cout << cnt << '\n';
        }
    }
    return 0;
}

---

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