Overview

By representing each transaction as a value that is “positive for deposits, negative for withdrawals,” and dynamically updating, this problem asks us to find “the first position where the cumulative sum reaches at least \(K\).”

This can be efficiently handled using a segment tree that maintains the interval sum and maximum prefix sum.

Analysis

We represent each transaction as a numerical value \(x_i\).

• When \(D_i = \texttt{R}\): \(x_i = B_i\)
• When \(D_i = \texttt{L}\): \(x_i = -B_i\)

Then, the balance after the \(i\)-th transaction is

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

A type \(2\) query becomes:

Find the smallest \(i\) such that \(S_i \geq K\)

Naive Approach

If we compute the cumulative sum from the beginning for each query, a single query takes \(O(N)\).

Since \(N, Q\) can be up to about \(2 \times 10^5\), the worst case is \(O(NQ)\), which is too slow.

Required Information

For a given interval, it is sufficient to maintain the following two pieces of information:

• sum: the total sum of the entire interval
• pref: the maximum prefix sum starting from the beginning of the interval

For example, if the interval values are

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

then:

• sum is \(3 - 5 + 10 = 8\)
• The prefix sums are \(3, -2, 8\), so pref is \(8\)

With this information, we can merge intervals.

Let the left interval be \(A\) and the right interval be \(B\). Then:

• The total sum is

\[ A.sum + B.sum \]

• The maximum prefix sum of the combined interval is whichever is larger:
  • The maximum within the left interval
  • The maximum achieved by passing through the entire left interval and then taking a prefix of the right interval

Therefore:

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

This allows us to manage interval information using a segment tree.

Algorithm

1. Information Stored in the Segment Tree

Each node stores the following:

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

• sum: the total of that interval
• pref: the maximum prefix sum within that interval

For leaves, given the transaction value \(x\):

sum = x
pref = x

2. Merging Nodes

Let a be the left node and b be the right node. The merged node is computed as follows:

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

This takes the maximum of “the maximum prefix sum is entirely within the left side” and “the case where we use all of the left side and extend into the right side.”

3. Update Operation

For operation 1 p D b, we change the value of the \(p\)-th transaction.

• If R, set it to \(+b\)
• If L, set it to \(-b\)

Then update the leaf of the segment tree.

After that, recompute information upward toward the root.

Since this is a segment tree, the update takes \(O(\log N)\).

4. Query Operation

For operation 2 K, we find the first position where the cumulative sum reaches at least \(K\).

First, the maximum prefix sum of the entire array is stored in the root seg[1].pref.

If

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

then the balance never reaches \(K\) after any transaction, so the answer is 0.

Otherwise, we descend from the root of the segment tree to find the first position where the sum reaches at least \(K\).

Let acc be the cumulative sum up to (but not including) the current node.

For the left child, if:

acc + seg[left].pref >= K

then the answer lies within the left interval.

Otherwise, \(K\) is not reached within the left interval, so we pass through the entire left interval:

acc += seg[left].sum

and proceed to the right child.

Repeating this until we reach a leaf gives us the transaction number of the answer.

Complexity

• Time complexity: \(O((N + Q)\log N)\)
  • Initial construction is \(O(N)\)
  • Each update/query is \(O(\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• The total of amounts can be up to about \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\), so use long long instead of int.
• For unused leaves in the segment tree (where no actual transaction exists), set pref to a very small value.
  • In the code, NEG = -(1LL << 60) is used.
• The output number is \(1\)-indexed, so for a leaf index idx, output:

idx - sz + 1

Source Code

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

---

This editorial was generated by gpt-5.5-xhigh.