概要

区間 \([l,r]\) のモンスターを、初期体力 \(d\) で左から順に処理したときに倒せる数を求めます。
点更新があるため、各区間の「体力ごとの結果」をセグメント木で管理します。

考察

体力やモンスターの強さはすべて \(0\) 以上 \(C\) 以下で、\(C \leq 50\) と非常に小さいです。

ここで重要なのは、ある区間について、

初期体力が \(h\) のとき、最終的に体力がいくつ残り、何体倒せるか

を、すべての \(h = 0,1,\dots,C\) について前計算しておけることです。

例えば、ある区間を表す情報として次の配列を持ちます。

• rem[h] : 初期体力 \(h\) でこの区間を処理した後の残り体力
• cnt[h] : 初期体力 \(h\) でこの区間を処理したときに倒せるモンスター数

これが分かっていれば、クエリ 2 l r d の答えは、その区間の cnt[d] になります。

---

素朴にクエリごとに \(l\) から \(r\) までシミュレーションすると、最悪で \(O(NQ)\) かかります。
\(N \leq 50000\), \(Q \leq 20000\) なので間に合いません。

そこで、区間の情報をセグメント木で管理します。

区間を左右に分けたとき、左区間を処理してから右区間を処理すればよいので、区間情報は合成できます。

左区間を \(L\)、右区間を \(R\) とします。
初期体力が \(h\) のとき、

1. 左区間を処理する

   • 残り体力は L.rem[h]
   • 倒した数は L.cnt[h]

2. その残り体力で右区間を処理する

   • 残り体力は R.rem[L.rem[h]]
   • 追加で倒す数は R.cnt[L.rem[h]]

したがって、結合後の区間では

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

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

となります。

このように、各ノードに長さ \(C+1\) の配列を持たせることで、点更新と区間クエリを高速に処理できます。

アルゴリズム

1. 1体のモンスターを表すノード

強さが \(a\) のモンスター 1 体について考えます。

初期体力 \(h\) に対して、

• \(h \geq a\) なら倒せる
  
  • 残り体力は \(h-a\)
  • 倒した数は \(1\)
• \(h < a\) なら倒せない
  
  • 残り体力は \(h\)
  • 倒した数は \(0\)

よって葉ノードは次のように作れます。

\[ \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} \]

特に \(a=0\) の場合は、どの体力でも倒せて、体力は減りません。

---

2. 空区間を表す単位元

セグメント木の区間クエリでは、空の区間を表すノードが必要です。

空区間では何も起こらないので、

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

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

です。

これを単位元として使います。

---

3. ノードのマージ

左の区間を L、右の区間を R とすると、マージ結果 res は次のようになります。

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

これは「左区間を先に処理して、その残り体力で右区間を処理する」という意味です。

---

4. 点更新

操作 1 p x では、\(p\) 番目のモンスターの強さを \(x\) に変更します。

1. 対応する葉ノードを強さ \(x\) のノードに作り直す
2. 親ノードを順に再計算する

セグメント木なので、更新にかかるノード数は \(O(\log N)\) 個です。
各ノードの再計算に \(O(C)\) かかるので、点更新全体は \(O(C \log N)\) です。

---

5. 区間クエリ

操作 2 l r d では、区間 \([l,r]\) のノード情報を求め、cnt[d] を出力します。

セグメント木では区間を複数のノードに分解して取得します。

ただし、今回のマージは順序が重要です。
左から右へ処理する必要があるため、

• 左側から集める結果 left_res
• 右側から集める結果 right_res

を別々に持ちます。

最後に

ans = merge_node(left_res, right_res);

として、区間全体の情報を得ます。

そして答えは

ans.cnt[d]

です。

計算量

• 時間計算量:
  • 構築: \(O(NC)\)
  • 1 回の更新: \(O(C \log N)\)
  • 1 回のクエリ: \(O(C \log N)\)
  • 全体: \(O(NC + QC \log N)\)
• 空間計算量: \(O(NC)\)

\(C \leq 50\) なので、各ノードで \(0\) から \(C\) までを全探索しても十分高速です。

実装のポイント

• Node には rem と cnt の 2 つの配列を持たせます。

• 空区間の単位元では、rem[h] = h, cnt[h] = 0 とします。

• マージは「左を処理してから右を処理する」順番で行います。

• 区間クエリではマージの順序を壊さないように、left_res と right_res を分けて管理します。

• 入力は \(1\)-indexed ですが、実装では \(0\)-indexed に直して扱います。

  ソースコード

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

---

この解説は gpt-5.5-xhigh によって生成されました。