モンスターの列に対して、体力 \(d\) から開始してその列のモンスターを順に相手にしたとき、\(\bigl(\)何体のモンスターを倒せるか\(,\) 体力がいくつ残るか\(\bigr)\) の組を返す関数を考えます。 整数の \(2\) つ組 \(p\) について、\(1\) つ目の要素を \(p _ 1\) 、\(2\) つ目の要素を \(p _ 2\) と書くことにします。

モンスターの強さがそれぞれ \((a _ 1,a _ 2,\ldots,a _ k)\) であるような列に対する上の関数を \(f _ {(a _ 1,a _ 2,\ldots,a _ k)}\) と書くことにします。 各クエリで求めるべきものは、\({f _ {(A _ l,A _ {l+1},\ldots,A _ r)}(d)} _ 1\) です。

列 \(A\) と \(B\) を連結した列 \(A{{}+\!\!\!\!{}+{}}B\) について、\(f _ {A{{}+\!\!{}+{}}B}\) を \(f _ A\) と \(f _ B\) で表すことを考えます。 体力 \(d\) で列 \(A\) のモンスターを順に相手すると、\({f _ A(d)} _ 1\) 体のモンスターを倒し、体力が \({f _ A(d)} _ 2\) になります。 このあと列 \(B\) のモンスターを順に相手するので、さらに \({f _ B\left({f _ A(d)} _ 2\right)} _ 1\) 体のモンスターを倒し、体力が \({f _ B\left({f _ A(d)} _ 2\right)} _ 2\) になることがわかります。 このことから、\[f _ {A{{}+\!\!{}+{}}B}(d)=\left({f _ A(d)} _ 1+{f _ B\left({f _ A(d)} _ 2\right)} _ 1,{f _ B\left({f _ A(d)} _ 2\right)} _ 2\right)\] となります。

セグメント木でこの関数を管理することを考えます。 この関数は非負整数から非負整数の \(2\) つ組への関数ですが、クエリに対して答えを出すためには \(0,1,\ldots,C\) の \(C+1\) 個の値に対する関数の値を管理しておけば十分です。

時間計算量は \(O((N+Q\log N)C)\) などになります。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <atcoder/segtree>
using namespace std;

int main() {
    static int N, C, Q;
    cin >> N >> C >> Q;
    vector<int> A(N);
    for (int& a : A) {
        cin >> a;
    }

    // 一体のモンスターからなる列に対応する関数
    auto single_monster = [](int a) {
        vector<pair<int, int>> ret(C + 1);
        // 体力が足りなければ倒せない
        for (int i = 0; i < a; ++i) {
            ret[i] = {0, i};
        }
        // 足りたら 1 体倒せる
        for (int i = a; i <= C; ++i) {
            ret[i] = {1, i - a};
        }
        return ret;
    };

    // セグメント木をつくる
    atcoder::segtree<vector<pair<int, int>>, [](auto lhs, auto rhs) {
        vector<pair<int, int>> ret(C + 1);
        for (int i = 0; i <= C; ++i) {
            auto [left_count, left_hp] = lhs[i]; // 左の列を先に倒して
            auto [right_count, right_hp] = rhs[left_hp]; // 残った体力で右を倒す
            ret[i] = {left_count + right_count, right_hp};
        }
        return ret;
    }, [] { // 単位元は空の列
        vector<pair<int, int>> ret(C + 1);
        for (int i = 0; i <= C; ++i) {
            ret[i] = {0, i};
        }
        return ret;
    }> segment_tree(A | views::transform(single_monster) | ranges::to<vector>());

    for (int i = 0; i < Q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int p, x;
            cin >> p >> x;
            --p; // 0-indexed にする
            segment_tree.set(p, single_monster(x)); // 体力 x のモンスターで更新
        } else {
            int l, r, d;
            cin >> l >> r >> d;
            --l; // l, r を 0-indexed 右半開区間にする
            cout << segment_tree.prod(l, r)[d].first << endl;
        }
    }
    return 0;
}

from atcoder import segtree


N, C, Q = map(int, input().split())
A = list(map(int, input().split()))

# 一体のモンスターからなる列に対応する関数
def single_monster(a):
    return [(0, i) for i in range(a)] + [(1, i - a) for i in range(a, C + 1)]

# 二つの列に対応する関数から連結した列に対応する関数を作る
def concat(left, right):
    return [(left[i][0] + right[left[i][1]][0], right[left[i][1]][1]) for i in range(C + 1)]

# セグメント木をつくる
segment_tree = segtree.SegTree(concat, [(0, i) for i in range(C + 1)], [single_monster(a) for a in A])

for i in range(Q):
    t, *q = map(int, input().split())
    if t == 1:
        p, x = q
        p -= 1 # 0-indexed にする
        segment_tree.set(p, single_monster(x)) # 体力 x のモンスターで更新
    else:
        l, r, d = q
        l -= 1 # l, r を 0-indexed 右半開区間にする
        print(segment_tree.prod(l, r)[d][0])