概要

モンスター列に対して「強さの更新」と「区間シミュレーション（体力を消費しながら倒せるモンスター数を数える）」を効率的に処理する問題です。体力の上限 \(C\) が小さい（\(C \leq 50\)）ことを利用し、セグメント木の各ノードに「入力体力→出力体力・倒した数」の対応表を持たせることで高速化します。

考察

素朴なアプローチの問題点

操作2をそのまま \(l\) から \(r\) まで1体ずつシミュレーションすると、1回の操作に \(O(N)\) かかり、\(Q\) 回で \(O(NQ)\) となります。\(N = 50000, Q = 20000\) のため最悪 \(10^9\) 程度で TLE の恐れがあります。

重要な気づき：\(C\) が小さい

体力は \(0\) 以上 \(C\) 以下の整数しか取りません。つまり、あるモンスター区間に対して「体力 \(d\) で突入したら、体力いくつで抜けて、何体倒せるか」という関数は、\(d = 0, 1, \dots, C\) の たった \(C+1\) 通り しか入力パターンがありません。

この関数をテーブルとして事前計算しておけば、2つの区間の関数を合成できます。左の区間に体力 \(d\) で入ると体力 \(h_1\) で出てくるので、それを右の区間の入力とすればよいのです。

合成の具体例

例えば \(C = 5\) で、左区間の関数が \(f\)、右区間の関数が \(g\) のとき：

• 体力 \(d=5\) で左区間に入る → 体力 \(f(5) = 3\), 倒した数 \(c_1 = 2\)
• 体力 \(3\) で右区間に入る → 体力 \(g(3) = 1\), 倒した数 \(c_2 = 1\)
• 全体：体力 \(5 \to 1\), 倒した数 \(= 2 + 1 = 3\)

アルゴリズム

セグメント木 を用い、各ノードに以下のテーブルを持たせます：

• out_hp[d]：体力 \(d\) で区間に突入したときの、出口での残り体力
• out_cnt[d]：体力 \(d\) で区間に突入したときの、倒したモンスター数

葉ノード（モンスター1体）の構築

モンスターの強さが \(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} \]

ノードのマージ（左の子 \(L\)・右の子 \(R\) → 親）

各 \(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] \]

操作の処理

• 操作1（更新）：対象の葉を再構築し、祖先を順にマージし直す。
• 操作2（クエリ）：セグメント木上で区間 \([l, r]\) に該当するノードを左から順に訪問し、現在の体力を更新しながら倒した数を累積する。区間全体がノードに収まる場合はテーブルを \(O(1)\) で参照するだけです。

計算量

• 時間計算量:

  • 構築：\(O(NC)\)（各ノードのマージに \(O(C)\)、ノード数 \(O(N)\)）
  • 更新1回：\(O(C \log N)\)（葉から根まで \(O(\log N)\) 個のノードをマージ）
  • クエリ1回：\(O(\log N)\)（訪問するノードで \(O(1)\) のテーブル参照）
  • 全体：\(O(NC + QC\log N)\)

• 空間計算量: \(O(NC)\)（セグメント木の各ノードにサイズ \(C+1\) の配列2本）

\(N = 50000, C = 50, Q = 20000\) のとき、更新は約 \(50 \times 16 \times 20000 = 1.6 \times 10^7\) 程度で十分高速です。

実装のポイント

• セグメント木の配列サイズは \(4N\) 程度確保する（コードでは 200001）。

• クエリでは、区間が完全にノードに含まれる場合はテーブルをそのまま返し、部分的に重なる場合は左右の子に再帰して結果を合成します。このとき 左の結果の出力体力を右の入力体力として渡す 点が核心です。

• \(C\) が小さいため、テーブルの列挙は単純なループで十分です。高速化のためにビット演算等は不要です。

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。