Overview

If we convert each transaction into a sequence where “deposit is \(+B_i\), withdrawal is \(-B_i\)”, then query 2 K becomes the problem of “finding the smallest position where the prefix sum first reaches \(K\) or more.”
To efficiently handle updates (point modifications) and this search, we use a segment tree that maintains interval sums and maximum prefix sums.

Analysis

First, we replace the transactions with an array \(A\) as follows:

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

Then, the balance after processing the \(i\)-th transaction is the prefix sum [ S_i = A_1 + A_2 + \cdots + A_i ] Query 2 K asks “find the smallest \(i\) such that \(S_i \ge K\) (or output 0 if none exists).”

---

Naively scanning the prefix sum from the beginning each time costs \(O(N)\) per query.
Since \(Q\) can be up to \(2\times 10^5\), the worst case becomes \(O(NQ)\), which is too slow.

Because there are also updates 1 p D b, we cannot rely solely on precomputation.
What we need is a data structure that supports both:

1. Point updates (modifying \(A_p\))
2. Fast search for “the first position where the prefix sum exceeds \(K\) when scanning from the beginning”

The key insight is to use a segment tree where each node stores: - sum: the interval sum - pref: the maximum prefix sum within that interval

When merging two child intervals \(L, R\): [ \text{sum} = L.\text{sum} + R.\text{sum} ] [ \text{pref} = \max(L.\text{pref},\ L.\text{sum} + R.\text{pref}) ] This is because “the maximum prefix either ends entirely within the left child, or uses the entire left child and extends into the right child” — there are only two cases.

Algorithm

1. Build array \(A\) from the initial transactions (R is positive, L is negative).
2. Construct the segment tree. Each leaf has:
   • sum = A_i
   • pref = max(0, A_i)
3. Process operations in order:
   • 1 p D b
     Update \(A_p\) to the new value (\(+b\) if R, \(-b\) if L), and perform a point update on the segment tree.
   • 2 K
     First check the root’s pref. If it is less than \(K\), the target is unreachable, so output 0.
     Otherwise, descend from the root:
     • Let acc be the accumulated prefix sum so far.
     • Look at the left child: if acc + left.pref >= K, the answer is in the left subtree, so go left.
     • Otherwise, set acc += left.sum and go right.
     • The leaf position reached is “the first transaction number where the prefix sum reaches \(K\) or more.”

The key point is that this descent always maintains “the earliest position.”

Complexity

• Time complexity: \(O((N+Q)\log N)\)
  
  • Construction \(O(N)\), each update/query is \(O(\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since amounts and prefix sums can become very large, use long long.

• The problem uses 1-indexed answers, so add +1 when outputting from internal 0-indexed representation.

• Since the leaf’s pref is set to max(0, A_i), unused positions (with value 0) are handled naturally.

• By checking root.pref < K first in firstAtLeast, the unreachable case can be handled concisely.

  Source Code

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

---

This editorial was generated by gpt-5.3-codex.