概要

各取引を「入金なら \(+B_i\)、出金なら \(-B_i\)」という数列に変換すると、質問 2 K は「累積和が初めて \(K\) 以上になる最小の位置」を求める問題になります。
更新（1点変更）とこの検索を高速に行うため、区間和と最大累積和（最大prefix和）を持つセグメント木を使います。

考察

まず、取引を次のような配列 \(A\) に置き換えます。

• R b \(\Rightarrow A_i = +b\)
• L b \(\Rightarrow A_i = -b\)

すると、\(i\) 件目処理後の残高は累積和 [ S_i = A_1 + A_2 + \cdots + A_i ] です。
質問 2 K は「\(S_i \ge K\) となる最小の \(i\) を求める（なければ 0）」です。

---

素朴に毎回先頭から累積和を見ていくと、質問1回あたり \(O(N)\)。
\(Q\) も最大 \(2\times 10^5\) なので最悪 \(O(NQ)\) となり間に合いません。

更新 1 p D b もあるため、前計算だけで済ませることもできません。
必要なのは以下を両立するデータ構造です。

1. 1点更新（\(A_p\) の変更）
2. 「先頭から見たとき累積和が初めて \(K\) を超える位置」の高速検索

ここで効くのが、各区間に - 区間和 sum - その区間内での最大prefix和 pref を持つセグメント木です。

2つの子区間 \(L, R\) をマージするときは [ \text{sum} = L.\text{sum} + R.\text{sum} ] [ \text{pref} = \max(L.\text{pref},\ L.\text{sum} + R.\text{pref}) ] となります。
これは「最大prefixは左だけで完結するか、左を全部使って右に入るか」の2択だからです。

アルゴリズム

1. 初期取引から配列 \(A\) を作る（R は正、L は負）。
2. セグメント木を構築。各葉は
   • sum = A_i
   • pref = max(0, A_i)
3. 操作を順に処理：
   • 1 p D b
     \(A_p\) を新しい値（Rなら \(+b\)、Lなら \(-b\)）に更新し、セグ木を1点更新。
   • 2 K
     まず根の pref を見る。これが \(K\) 未満なら到達不能なので 0。
     そうでなければ木を上から降りる：
     • 現在までの累積和を acc とする。
     • 左子を見て acc + left.pref >= K なら答えは左側にあるので左へ。
     • そうでなければ acc += left.sum として右へ。
     • 葉に着いた位置が「初めて \(K\) 以上になる取引番号」。

この降下で常に「最初の位置」を保てるのがポイントです。

計算量

• 時間計算量: \(O((N+Q)\log N)\)
  
  • 構築 \(O(N)\)、各更新/質問が \(O(\log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 金額・累積和は最大で大きくなるため long long を使う。

• 質問の答えは問題文が 1-indexed なので、内部0-indexから +1 して出力。

• セグ木の葉の pref を max(0, A_i) にしているため、未使用領域（0）を含んでも自然に扱える。

• firstAtLeast で root.pref < K を先に判定すると、到達不能ケースを簡潔に処理できる。

  ソースコード

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

struct SegTree {
    struct Node {
        long long sum;
        long long pref; // maximum prefix sum
    };
    int n;
    vector<Node> st;

    static Node mergeNode(const Node& a, const Node& b) {
        return Node{
            a.sum + b.sum,
            max(a.pref, a.sum + b.pref)
        };
    }

    SegTree(const vector<long long>& arr) {
        int sz = (int)arr.size();
        n = 1;
        while (n < sz) n <<= 1;
        st.assign(2 * n, Node{0LL, 0LL});
        for (int i = 0; i < sz; i++) {
            st[n + i] = Node{arr[i], max(0LL, arr[i])};
        }
        for (int i = n - 1; i >= 1; i--) {
            st[i] = mergeNode(st[i << 1], st[i << 1 | 1]);
        }
    }

    void pointUpdate(int idx, long long val) {
        int p = idx + n;
        st[p] = Node{val, max(0LL, val)};
        p >>= 1;
        while (p) {
            st[p] = mergeNode(st[p << 1], st[p << 1 | 1]);
            p >>= 1;
        }
    }

    // return first index i (0-based) such that prefix sum up to i >= K, else -1
    int firstAtLeast(long long K) const {
        if (st[1].pref < K) return -1;
        int v = 1;
        long long acc = 0;
        while (v < n) {
            const Node& L = st[v << 1];
            if (acc + L.pref >= K) {
                v = v << 1;
            } else {
                acc += L.sum;
                v = v << 1 | 1;
            }
        }
        return v - n;
    }
};

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

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

    vector<char> D(N);
    vector<long long> B(N);
    vector<long long> A(N);

    for (int i = 0; i < N; i++) {
        cin >> D[i] >> B[i];
        A[i] = (D[i] == 'R' ? B[i] : -B[i]);
    }

    SegTree seg(A);

    for (int qi = 0; qi < Q; qi++) {
        int t;
        cin >> t;
        if (t == 1) {
            int p;
            char nd;
            long long b;
            cin >> p >> nd >> b;
            --p;
            D[p] = nd;
            B[p] = b;
            long long v = (nd == 'R' ? b : -b);
            seg.pointUpdate(p, v);
        } else {
            long long K;
            cin >> K;
            int idx = seg.firstAtLeast(K);
            if (idx == -1 || idx >= N) cout << 0 << '\n';
            else cout << (idx + 1) << '\n';
        }
    }

    return 0;
}

---

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