概要

各取引を「入金なら正、出金なら負」の値として見て、動的に更新しながら「累積和が初めて \(K\) 以上になる位置」を答える問題です。

これは、区間の総和と最大 prefix 和を持つセグメント木で効率よく処理できます。

考察

各取引を数値 \(x_i\) として表します。

• \(D_i = \texttt{R}\) のとき \(x_i = B_i\)
• \(D_i = \texttt{L}\) のとき \(x_i = -B_i\)

すると、\(i\) 番目の取引後の残高は

\[ S_i = x_1 + x_2 + \cdots + x_i \]

です。

タイプ \(2\) の質問は、

最小の \(i\) で \(S_i \geq K\) となるものを求める

という問題になります。

素朴な方法

質問ごとに \(1\) 番目から順に累積和を計算すると、\(1\) 回の質問に \(O(N)\) かかります。

\(N, Q\) は最大で \(2 \times 10^5\) 程度なので、最悪で \(O(NQ)\) となり間に合いません。

必要な情報

ある区間について、次の \(2\) つの情報を持てば十分です。

• sum：その区間全体の和
• pref：その区間の先頭から見た最大 prefix 和

例えば区間の値が

\[ [3, -5, 10] \]

なら、

• sum は \(3 - 5 + 10 = 8\)
• prefix 和は \(3, -2, 8\) なので pref は \(8\)

です。

この情報を持つと、区間を結合できます。

左区間を \(A\)、右区間を \(B\) とすると、

• 全体の和は

\[ A.sum + B.sum \]

• 全体の最大 prefix 和は、
  • 左区間の中で最大になる
  • 左区間をすべて通ったあと、右区間の prefix で最大になる

のどちらかなので、

\[ \max(A.pref,\ A.sum + B.pref) \]

になります。

これにより、セグメント木で各区間の情報を管理できます。

アルゴリズム

1. セグメント木に持たせる情報

各ノードに以下を持たせます。

struct Node {
    long long sum;
    long long pref;
};

• sum：その区間の合計
• pref：その区間内の最大 prefix 和

葉では、取引の値を \(x\) として

sum = x
pref = x

とします。

2. ノードのマージ

左のノードを a、右のノードを b とすると、結合後のノードは次のようになります。

sum = a.sum + b.sum
pref = max(a.pref, a.sum + b.pref)

これは、「最大 prefix 和が左側で完結する場合」と「左側を全部使って右側に入る場合」の最大を取っています。

3. 更新操作

操作 1 p D b では、\(p\) 番目の取引の値を変更します。

• R なら \(+b\)
• L なら \(-b\)

にして、セグメント木の葉を更新します。

その後、親方向に情報を再計算します。

更新はセグメント木なので \(O(\log N)\) です。

4. 質問操作

操作 2 K では、初めて累積和が \(K\) 以上になる位置を求めます。

まず、全体の最大 prefix 和はセグメント木の根 seg[1].pref に入っています。

もし

\[ seg[1].pref < K \]

なら、どの取引後にも残高は \(K\) 以上にならないので、答えは 0 です。

そうでなければ、セグメント木を根から降りて、最初に \(K\) 以上になる位置を探します。

現在のノードより前までの累積和を acc とします。

左の子について、

acc + seg[left].pref >= K

なら、左区間の中に答えがあります。

そうでなければ、左区間では \(K\) に到達しないので、左区間全体を通過します。

acc += seg[left].sum

として、右の子に進みます。

これを葉まで繰り返すと、答えの取引番号が得られます。

計算量

• 時間計算量: \(O((N + Q)\log N)\)
  • 初期構築は \(O(N)\)
  • 各更新・質問は \(O(\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 金額の合計は最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) 程度になるため、int ではなく long long を使います。
• セグメント木の余った葉には、実際の取引が存在しないため、pref を非常に小さい値にしておきます。
  • コードでは NEG = -(1LL << 60) を使っています。
• 出力する番号は \(1\) 始まりなので、葉の添字 idx に対して

idx - sz + 1

を出力します。

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long sum;
    long long pref;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    const long long NEG = -(1LL << 60);

    int sz = 1;
    while (sz < N) sz <<= 1;

    vector<Node> seg(2 * sz, {0, NEG});

    auto merge_node = [](const Node& a, const Node& b) -> Node {
        return {a.sum + b.sum, max(a.pref, a.sum + b.pref)};
    };

    auto signed_value = [](char D, long long B) -> long long {
        return D == 'R' ? B : -B;
    };

    for (int i = 0; i < N; i++) {
        char D;
        long long B;
        cin >> D >> B;
        long long x = signed_value(D, B);
        seg[sz + i] = {x, x};
    }

    for (int i = sz - 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;
            char D;
            long long b;
            cin >> p >> D >> b;

            long long x = signed_value(D, b);
            int idx = sz + p - 1;
            seg[idx] = {x, x};

            idx >>= 1;
            while (idx >= 1) {
                seg[idx] = merge_node(seg[idx << 1], seg[idx << 1 | 1]);
                idx >>= 1;
            }
        } else {
            long long K;
            cin >> K;

            if (seg[1].pref < K) {
                cout << 0 << '\n';
                continue;
            }

            int idx = 1;
            long long acc = 0;

            while (idx < sz) {
                int left = idx << 1;
                if (acc + seg[left].pref >= K) {
                    idx = left;
                } else {
                    acc += seg[left].sum;
                    idx = left | 1;
                }
            }

            cout << idx - sz + 1 << '\n';
        }
    }

    return 0;
}

---

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