Overview

Each transaction is treated as a value that is “positive for deposits, negative for withdrawals.” The problem asks us to find “the first position where the prefix sum reaches at least \(K\)” while performing point updates.

Since the prefix sum can decrease along the way, we cannot use simple binary search. Instead, we use a segment tree that maintains the “total sum” and “maximum prefix sum” of each interval.

Analysis

We convert the \(i\)-th transaction to the following value \(A_i\):

• For R B: \(A_i = B\)
• For L B: \(A_i = -B\)

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

\[ S_i = A_1 + A_2 + \cdots + A_i \]

For type \(2\) queries, we need to find the first \(i\) such that

\[ S_i \geq K \]

Naive Approach

If we compute the prefix sum from the beginning for each query, one query takes \(O(N)\).

Since \(N, Q\) are at most \(2 \times 10^5\), the worst case is

\[ O(NQ) \]

which is too slow.

Simple Binary Search Does Not Work

If the prefix sum \(S_i\) were monotonically increasing, we could use binary search, but due to withdrawals L, the prefix sum can decrease.

For example, if

\[ A = [10, -8, 10] \]

then the prefix sums are

\[ [10, 2, 12] \]

which is not monotonic.

Therefore, ordinary binary search cannot find the correct answer.

Key Insight

For a given interval, we only need to maintain the following two values:

1. The total sum of the entire interval
2. The maximum prefix sum within the interval

The maximum prefix sum of interval \([l, r]\) is defined as:

\[ \max_{l \leq t \leq r}(A_l + A_{l+1} + \cdots + A_t) \]

With this information, we can determine “whether the balance reaches at least \(K\) somewhere within this interval.”

Algorithm

We use a segment tree.

For the interval represented by each node, we maintain the following:

• sum: the total sum of the entire interval
• pref: the maximum prefix sum of the interval

For a leaf, i.e., a single element \(x\):

\[ sum = x \]

\[ pref = x \]

Merging Intervals

Let the left interval be \(L\) and the right interval be \(R\).

The total sum of the combined interval is simply:

\[ sum = sum_L + sum_R \]

The maximum prefix sum is one of the following:

1. The maximum is achieved entirely within the left interval
2. The maximum is achieved by passing through the entire left interval and continuing partway into the right interval

Therefore:

\[ pref = \max(pref_L, sum_L + pref_R) \]

Update Query

For 1 p D b, we update the \(p\)-th value.

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

We update the leaf of the segment tree, then recompute sum and pref upward toward the root.

This takes \(O(\log N)\).

Answer Query

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

First, we check the overall maximum prefix sum seg_pref[1].

If

\[ seg\_pref[1] < K \]

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

Otherwise, we descend from the top of the segment tree.

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

For the left child, if

\[ acc + pref_{\text{left}} \geq K \]

then the answer lies within the left child’s interval.

Otherwise, the balance does not reach \(K\) within the left child’s interval, so we treat the entire left interval as processed:

\[ acc \leftarrow acc + sum_{\text{left}} \]

and proceed to the right child.

By repeating this until we reach a leaf, we find the transaction number where the balance first reaches at least \(K\).

Complexity

• Time complexity: \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• R is treated as a positive value, L as a negative value.

• Each node in the segment tree holds two values: sum and pref.

• To align the array size to a power of \(2\), there may be leaves that do not correspond to actual transactions.

  • The sum of such leaves is \(0\).
  • The pref is set to a sufficiently large negative value so that it does not affect the answer.

• In Python, integers have arbitrary precision so there is no concern about overflow, but in other languages, \(64\)-bit integers are required.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())

    size = 1
    while size < N:
        size <<= 1

    NEG = -10**30
    seg_sum = [0] * (2 * size)
    seg_pref = [NEG] * (2 * size)

    for i in range(N):
        D, B = input().split()
        v = int(B)
        if D == b'L':
            v = -v
        idx = size + i
        seg_sum[idx] = v
        seg_pref[idx] = v

    for i in range(size - 1, 0, -1):
        l = i << 1
        r = l | 1
        sl = seg_sum[l]
        seg_sum[i] = sl + seg_sum[r]
        a = seg_pref[l]
        b = sl + seg_pref[r]
        seg_pref[i] = a if a >= b else b

    ans = []

    for _ in range(Q):
        q = input().split()

        if q[0] == b'1':
            p = int(q[1])
            D = q[2]
            b = int(q[3])
            if D == b'L':
                b = -b

            idx = size + p - 1
            seg_sum[idx] = b
            seg_pref[idx] = b

            idx >>= 1
            while idx:
                l = idx << 1
                r = l | 1
                sl = seg_sum[l]
                seg_sum[idx] = sl + seg_sum[r]
                a = seg_pref[l]
                c = sl + seg_pref[r]
                seg_pref[idx] = a if a >= c else c
                idx >>= 1

        else:
            K = int(q[1])

            if seg_pref[1] < K:
                ans.append("0")
                continue

            idx = 1
            acc = 0
            while idx < size:
                l = idx << 1
                if acc + seg_pref[l] >= K:
                    idx = l
                else:
                    acc += seg_sum[l]
                    idx = l | 1

            ans.append(str(idx - size + 1))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.