Overview

This problem requires efficiently finding “the transaction number where the balance first reaches \(K\) or more” while dynamically updating transactions in a ledger. It is solved using binary search on a segment tree.

Analysis

Convert each transaction to a numerical value. If it’s a deposit (R), use \(+B_i\); if it’s a withdrawal (L), use \(-B_i\). Then the balance after the \(i\)-th transaction is \(\sum_{j=1}^{i} \text{val}[j]\) (prefix sum).

Naive approach: For each type-2 query, compute the prefix sum from left to right and find the first position where it reaches \(K\) or more → This takes \(O(N)\) per query, and with many queries results in \(O(NQ)\), which causes TLE.

Key insight: The problem of “finding the first position where the prefix sum reaches \(K\) or more” can be solved in \(O(\log N)\) by maintaining the maximum prefix sum of each interval in a segment tree and descending through the tree.

Algorithm

Segment Tree Design

Each node stores the following two values: - sum: the total value of the interval - max_prefix: the maximum prefix sum within the interval (the maximum cumulative sum reached when starting from the left end of the interval)

Merge rule (computing the parent from left child \(L\) and right child \(R\)): - sum = \(L.\text{sum} + R.\text{sum}\) - max_prefix = \(\max(L.\text{max\_prefix},\ L.\text{sum} + R.\text{max\_prefix})\)

Intuitively, the maximum prefix sum of the entire interval is the larger of “the maximum achieved within the left half alone” or “the maximum achieved in the right half after passing through the entire left half.”

Query Processing (Binary Search on the Segment Tree)

Recursively find “given that the accumulated sum from the left is accumulated, what is the first position within this node’s interval where the sum reaches \(K\) or more?”

1. If it’s a leaf node: check whether accumulated + sum >= K
2. If it’s an internal node:
   • If left child’s max_prefix + accumulated \(\geq K\) → the answer is in the left child
   • Otherwise → pass through the left child’s interval (accumulated += left child's sum) and search the right child

Concrete Example

If the transactions are \([+3, -1, +5, -2]\): - The prefix sums are \([3, 2, 7, 5]\) - For a query with \(K = 6\), the first time it reaches 6 or more is the 3rd transaction (prefix sum 7) → the answer is 3

Complexity

• Time complexity: \(O((N + Q) \log N)\)
  • Construction: \(O(N)\)
  • Each operation (update/query): \(O(\log N)\)
• Space complexity: \(O(N)\) (segment tree array size)

Implementation Notes

• Convert transaction values to \(+B\) for R and \(-B\) for L for management.

• Since the maximum value of \(K\) is \(2 \times 10^{14}\), long long must be used.

• If the segment tree’s overall max_prefix (the root’s value) is less than \(K\), the sum never reaches \(K\) or more anywhere, so immediately return \(0\).

• Binary search on the segment tree operates in \(O(\log N)\), which is more efficient than the typical approach of interval query + binary search (\(O(\log^2 N)\)).

  Source Code

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

---

This editorial was generated by claude4.6opus-thinking.