概要

家計簿の取引を動的に更新しながら、「残高が初めて \(K\) 以上になる取引番号」を効率的に求める問題です。セグメント木上の二分探索で解きます。

考察

各取引を数値に変換します。入金 (R) なら \(+B_i\)、出金 (L) なら \(-B_i\) とすると、\(i\) 番目の取引後の残高は \(\sum_{j=1}^{i} \text{val}[j]\)（累積和）です。

素朴なアプローチ: タイプ2のクエリごとに左から順に累積和を計算し、初めて \(K\) 以上になる位置を探す → \(O(N)\) かかり、クエリが多いと \(O(NQ)\) で TLE。

重要な気づき: 「累積和が初めて \(K\) 以上になる最初の位置」を求める問題は、セグメント木に区間の最大プレフィックス和（prefix max）を持たせることで、木の上を降りながら \(O(\log N)\) で解けます。

アルゴリズム

セグメント木の設計

各ノードに以下の2つの値を持たせます： - sum：区間の合計値 - max_prefix：区間内の最大プレフィックス和（区間の左端から始めたとき、途中で到達する累積和の最大値）

マージ規則（左の子 \(L\)、右の子 \(R\) から親を計算）： - sum = \(L.\text{sum} + R.\text{sum}\) - max_prefix = \(\max(L.\text{max\_prefix},\ L.\text{sum} + R.\text{max\_prefix})\)

直感的には、区間全体の最大プレフィックス和は「左半分だけで最大になるか、左半分を全部通過した後に右半分で最大になるか」の大きい方です。

クエリの処理（セグメント木上の二分探索）

「左側からの累積が accumulated のとき、このノードの区間内で初めて \(K\) 以上になる位置はどこか？」を再帰的に求めます。

1. 葉ノードなら：accumulated + sum >= K か判定
2. 内部ノードなら：
   • 左の子の max_prefix + accumulated \(\geq K\) → 答えは左の子にある
   • そうでなければ → 左の子の区間を通過（accumulated += 左の子のsum）し、右の子を探索

具体例

取引が \([+3, -1, +5, -2]\) の場合： - 累積和は \([3, 2, 7, 5]\) - \(K = 6\) のクエリなら、初めて6以上になるのは3番目（累積和7）→ 答えは3

計算量

• 時間計算量: \(O((N + Q) \log N)\)
  • 構築: \(O(N)\)
  • 各操作（更新・クエリ）: \(O(\log N)\)
• 空間計算量: \(O(N)\)（セグメント木の配列サイズ）

実装のポイント

• 取引の値は R なら \(+B\)、L なら \(-B\) に変換して管理する。

• \(K\) の最大値が \(2 \times 10^{14}\) なので、long long を使う必要がある。

• セグメント木全体の max_prefix（根の値）が \(K\) 未満なら、どこでも \(K\) 以上にならないので即座に \(0\) を返す。

• セグメント木上の二分探索は、通常の区間クエリ＋二分探索（\(O(\log^2 N)\)）より効率的な \(O(\log N)\) で動作する。

  ソースコード

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

struct Node {
    long long sum;
    long long max_prefix;
};

const int MAXN = 200005;
Node tree[4 * MAXN];
int n, q;
long long val[MAXN];

void build(int node, int l, int r) {
    if (l == r) {
        tree[node].sum = val[l];
        tree[node].max_prefix = val[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
    tree[node].max_prefix = max(tree[2*node].max_prefix, tree[2*node].sum + tree[2*node+1].max_prefix);
}

void update(int node, int l, int r, int pos, long long newval) {
    if (l == r) {
        tree[node].sum = newval;
        tree[node].max_prefix = newval;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(2*node, l, mid, pos, newval);
    else update(2*node+1, mid+1, r, pos, newval);
    tree[node].sum = tree[2*node].sum + tree[2*node+1].sum;
    tree[node].max_prefix = max(tree[2*node].max_prefix, tree[2*node].sum + tree[2*node+1].max_prefix);
}

int query(int node, int l, int r, long long K, long long accumulated) {
    if (l == r) {
        if (accumulated + tree[node].sum >= K) return l;
        else return 0;
    }
    int mid = (l + r) / 2;
    if (accumulated + tree[2*node].max_prefix >= K) {
        return query(2*node, l, mid, K, accumulated);
    } else {
        return query(2*node+1, mid+1, r, K, accumulated + tree[2*node].sum);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        char d;
        long long b;
        cin >> d >> b;
        if (d == 'R') val[i] = b;
        else val[i] = -b;
    }
    
    build(1, 1, n);
    
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int p;
            char d;
            long long b;
            cin >> p >> d >> b;
            long long newval = (d == 'R') ? b : -b;
            val[p] = newval;
            update(1, 1, n, p, newval);
        } else {
            long long K;
            cin >> K;
            if (tree[1].max_prefix < K) {
                cout << 0 << '\n';
            } else {
                cout << query(1, 1, n, K, 0) << '\n';
            }
        }
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。