概要

一列に並んだモンスターに対し、「強さの更新」と「特定の区間で何体倒せるかのシミュレーション」を行う問題です。最大体力 \(C\) が \(50\) と非常に小さいことを利用して、セグメント木に各体力ごとの結果を保持させることで効率的に解くことができます。

考察

1. 素朴なシミュレーションの限界

クエリ 2 l r d に対して、毎回 \(l\) 番目から \(r\) 番目まで愚直に計算すると、1回のクエリに最大で \(O(N)\) かかります。クエリ数が \(Q\) なので、全体の計算量は \(O(NQ)\) となり、今回の制約（\(N=50,000, Q=20,000\)）では実行時間制限に間に合いません。

2. 体力の上限 \(C\) の小ささに注目

この問題の最大の特徴は、モンスターの強さと体力の最大値 \(C\) が \(50\) と非常に小さい点です。 ある連続した区間のモンスターたちについて、「その区間に体力 \(h\) で突入したとき、最終的な体力はどうなり、何体のモンスターを倒せるか」という情報は、すべての \(h \in [0, C]\) について事前に計算しておくことが可能です。

3. セグメント木の活用

「区間の情報を統合する」という性質から、セグメント木の利用が考えられます。セグメント木の各ノードに、以下の情報を配列として持たせます。

• next_h[h] : 体力 \(h\) でこの区間に入ったとき、区間を抜けた後の残り体力
• count[h] : 体力 \(h\) でこの区間に入ったとき、この区間で倒せたモンスターの総数

2つのノード（左の子 \(L\) と右の子 \(R\)）をマージする際は、以下のようになります。 1. 左の区間に体力 \(h\) で入る。 2. 左を抜けた後の体力は \(mid\_h = L.next\_h[h]\) となり、倒した数は \(L.count[h]\)。 3. 次に右の区間に体力 \(mid\_h\) で入る。 4. 右を抜けた後の体力は \(R.next\_h[mid\_h]\) となり、追加で倒した数は \(R.count[mid\_h]\)。

これを全 \(h\) について計算することで、親ノードの情報を \(O(C)\) で作成できます。

アルゴリズム

1. セグメント木の構築:
   • 葉ノード（モンスター \(i\)）：体力 \(h\) に対して、\(h \geq A_i\) なら next_h = h - A_i, count = 1、そうでなければ next_h = h, count = 0 と設定します。
   • 中間ノード：左右の子を上記のマージルールに従って合成します。
2. 点更新（クエリ1）:
   • 指定されたモンスターの葉ノードを更新し、ルートに向かって \(O(C \log N)\) で再計算します。
3. 範囲クエリ（クエリ2）:
   • 範囲 \([l, r]\) をカバーする \(O(\log N)\) 個のノードを抽出します。
   • 初期体力 \(d\) を使って、抽出したノードを左から順に走査し、現在の体力を更新しながら倒したモンスターの合計を求めます。

計算量

• 時間計算量: \(O((N + Q \log N) \cdot C)\)
  • セグメント木の構築に \(O(NC)\)
  • 各更新に \(O(C \log N)\)
  • 各クエリに \(O(\log N)\)（またはノードの合成を含めて \(O(C \log N)\) ですが、今回は単一の \(d\) についてのみ辿ればよいため \(O(\log N)\) です）
• 空間計算量: \(O(N \cdot C)\)
  • セグメント木の各ノードにサイズ \(C\) の配列を2つ持つためです。

実装のポイント

• メモリ管理: \(C\) が小さいため、next_h を保持する配列には signed char などの小さいデータ型を使うことで、メモリ使用量を節約できます。

• クエリ処理: 範囲 \([l, r]\) に対応するノードをリストアップし、それらを順番に処理する際、常に「現在の体力」を引き継いで次のノードの count と next_h を参照していくのがコツです。

  ソースコード

#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;
}

---

この解説は gemini-3-flash-thinking によって生成されました。