概要

各区間について「初期HP \(d\) を入れたとき、区間通過後のHPと倒した数」が分かれば、クエリ 2 l r d は高速に処理できます。
\(C \le 50\) と小さいことを活かし、セグメント木の各ノードに HP ごとの遷移表を持たせて、更新と区間クエリを両方高速化します。

考察

この問題の厄介な点は、クエリ 2 が単なる和や最小値ではなく、「現在HPに応じて次の結果が変わる」という状態依存な処理であることです。

例えばモンスター1体（強さ \(a\)）なら、初期HP \(d\) に対して：

• \(d \ge a\) なら倒せる（撃破数+1、HPは \(d-a\)）
• \(d < a\) なら倒せない（撃破数+0、HPは \(d\)）

つまり1体のモンスターは、HP \(d\) を入力として
「(次のHP, 撃破数増分)」を返す関数とみなせます。

---

素朴に 2 l r d を毎回シミュレーションすると、1クエリ \(O(r-l+1)\)、最悪で \(O(N)\)。
これを \(Q\) 回行うと最悪 \(O(NQ)\) で、\(N=50000, Q=20000\) では間に合いません。

---

ここで重要な観察は：

• HP は \(0..C\) の \(C+1\) 通りしかない（しかも \(C \le 50\)）
• 区間全体も「初期HPごとの遷移表」を持てる
• 2つの隣接区間の遷移表は合成できる

左区間を \(L\)、右区間を \(R\) とすると、初期HP \(d\) に対して：

1. まず左を通す → 中間HP \(m = L.rem[d]\)、撃破数 \(L.cnt[d]\)
2. 次に右を通す → 最終HP \(R.rem[m]\)、撃破数 \(R.cnt[m]\)

よって親区間は - rem[d] = R.rem[L.rem[d]] - cnt[d] = L.cnt[d] + R.cnt[L.rem[d]]

この「関数合成」ができるので、セグメント木に非常に相性が良いです。

アルゴリズム

各セグメント木ノードに以下を持たせます（長さ \(C+1\) の配列）：

• rem[d]: その区間を初期HP \(d\) で処理後の残りHP
• cnt[d]: その区間で倒せるモンスター数

1. 葉ノードの作成

1体（強さ val）に対して、全 \(d=0..C\) を列挙： - \(d \ge val\) なら rem[d]=d-val, cnt[d]=1 - それ以外は rem[d]=d, cnt[d]=0

2. ノードのマージ

左右ノード L, R から親 P を作る： - mid = L.rem[d] - P.rem[d] = R.rem[mid] - P.cnt[d] = L.cnt[d] + R.cnt[mid]

これを全 \(d=0..C\) で行う。

3. 更新クエリ 1 p x

位置 p の葉を新しい強さ x で作り直し、帰りがけにマージして再計算。
セグ木の高さぶんで処理できる。

4. 取得クエリ 2 l r d

通常の区間クエリと同様に再帰しつつ、
「現在HPを左結果の残HPで右へ渡す」ように順序を守って合成する。

コードの query は {残HP, 撃破数} を返していて、 - 範囲外は恒等変換として {hp, 0} - 完全被覆ならノード表を直接参照 {rem[hp], cnt[hp]} - 部分被覆なら左→右の順に処理して合成

これで正しい撃破数が得られます。

計算量

• 時間計算量:
  
  • 構築: \(O(NC)\)
    
  • 更新1回: \(O(C \log N)\)
    
  • クエリ1回: \(O(\log N)\) 回ノード訪問で各ノードは \(O(1)\) 参照（再帰合成のみ）なので実質 \(O(\log N)\)
    （ただし構築・更新でのマージは \(O(C)\)）
• 空間計算量: \(O(NC)\)（各ノードが長さ \(C+1\) の配列を2本持つ）

実装のポイント

• この解法の本質は「区間をHP遷移関数として持つ」ことです。
  

• query で左区間を先に処理し、その残HPを右に渡す順序が重要です（順序を逆にすると誤答）。

• rem は値域が \(0..C\) なので unsigned char で省メモリ化しています（\(C \le 50\) のため安全）。

• 範囲外返却を {hp,0}（恒等変換）にすると、再帰合成がきれいに書けます。

  ソースコード

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

---

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