Overview

This problem requires efficiently finding “the position where the cumulative sum first reaches \(K\) or more” over a sequence of values (deposits and withdrawals) that gets updated.

Analysis

1. Naive Approach and Its Limitations

If we compute the cumulative sum sequentially from the 1st transaction for each query, a single query takes up to \(O(N)\) time. If the number of queries is \(Q\), the total time complexity becomes \(O(NQ)\), which will not fit within the time limit given the constraints \(N, Q \leq 2 \times 10^5\).

2. Properties of Cumulative Sums and Updates

Since transactions are updated, precomputing cumulative sums cannot be used directly. Additionally, because withdrawals (negative values) exist, the cumulative sum is not necessarily monotonically increasing. Therefore, applying binary search on the cumulative sum array is also difficult.

3. Speeding Up with a Segment Tree

By using a segment tree that can manage “the total value of an interval” and “the maximum cumulative sum within an interval,” we can speed up both updates and searches. Each node holds the following two pieces of information: - sum: The total of transaction amounts contained in that interval - max_p: The maximum value of the cumulative sum within the interval, starting from the left end of that interval

When combining two nodes (left child L, right child R) to create a parent node, the parent’s max_p is the larger of the following: 1. When the maximum is reached within the left child’s interval: L.max_p 2. When we pass through the entire left child and the maximum is reached within the right child’s interval: L.sum + R.max_p

By maintaining information this way, we can perform “binary search on the segment tree,” descending through the segment tree in a manner similar to binary search.

Algorithm

Segment Tree Construction

1. Set the transaction value at each leaf node (positive for R, negative for L).
2. From bottom to top, fill in nodes according to the rules described above (sum and max_p).

Type 1: Modifying a Transaction

Update the leaf node at the specified index, then recompute sum and max_p going up toward the root. This can be done in \(O(\log N)\).

Type 2: Searching for the Target Balance

Starting from the root, perform the following checks to find the target transaction number: - Let current_sum be the current cumulative sum. - Using the left child’s max_p, determine whether current_sum + left.max_p >= K. - YES: It is guaranteed that \(K\) is first exceeded somewhere within the left child’s interval, so proceed to the left child. - NO: \(K\) is not reached within the left child’s interval, so proceed to the right child. At this point, add the left child’s sum to current_sum.

This search also completes in \(O(\log N)\) steps (the height of the tree).

Complexity

• Time Complexity: \(O((N + Q) \log N)\)
  • Building the segment tree takes \(O(N)\), and each query (update or search) takes \(O(\log N)\).
• Space Complexity: \(O(N)\)
  • The number of nodes in the segment tree requires at most approximately \(4N\).

Implementation Notes

• Handling large values: Since cumulative sums can reach approximately \(2 \times 10^{14}\), it is necessary to use long long type in C++.

• Search termination condition: If the root node’s max_p is less than \(K\), then \(K\) cannot be reached anywhere in the array, so we can immediately output 0.

• Segment tree size: Using the smallest power of 2 greater than or equal to \(N\) as the number of leaves simplifies the implementation.

  Source Code

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

/**
 * Problem: Household Account Book and Target Balance
 * We need to maintain prefix sums of transactions and find the first transaction 
 * such that the prefix sum reaches or exceeds a given target K.
 * Transactions can be additions (R) or subtractions (L).
 *
 * Approach:
 * Use a Segment Tree where each node stores:
 * 1. The total sum of elements in its range.
 * 2. The maximum prefix sum within its range (relative to the start of the range).
 *
 * Time Complexity:
 * - Build: O(N)
 * - Update: O(log N)
 * - Query (Type 2): O(log N)
 * Total: O((N + Q) log N)
 */

struct Node {
    long long sum;
    long long max_p;
};

// N <= 2e5, so tree_size is up to 2^18 = 262144.
// 2 * tree_size is up to 524288. MAX_NODES = 1 << 19 is sufficient.
const int MAX_NODES = 1 << 19;
Node tree[MAX_NODES];
int tree_size;

/**
 * Update the p-th transaction (0-indexed) with a new value.
 */
void update(int i, long long val) {
    i += tree_size;
    tree[i] = {val, val};
    while (i > 1) {
        i /= 2;
        int left = 2 * i;
        int right = 2 * i + 1;
        tree[i].sum = tree[left].sum + tree[right].sum;
        // The max prefix sum of the merged range is the maximum of:
        // 1. Max prefix sum of the left child.
        // 2. Sum of the left child + max prefix sum of the right child.
        tree[i].max_p = max(tree[left].max_p, tree[left].sum + tree[right].max_p);
    }
}

/**
 * Traverse the segment tree to find the first index where the global prefix sum >= K.
 * current_sum is the sum of all elements to the left of the current node's range.
 */
int find_first(int node, int l, int r, long long current_sum, long long K) {
    if (l == r) {
        return l;
    }
    int mid = l + (r - l) / 2;
    int left_child = 2 * node;
    int right_child = 2 * node + 1;

    // Check if the target K is reached within the left child's range.
    if (current_sum + tree[left_child].max_p >= K) {
        return find_first(left_child, l, mid, current_sum, K);
    } else {
        // Otherwise, the first occurrence must be in the right child's range.
        return find_first(right_child, mid + 1, r, current_sum + tree[left_child].sum, K);
    }
}

int main() {
    // Fast I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // Determine the smallest power of 2 >= N for the segment tree leaves.
    tree_size = 1;
    while (tree_size < N) tree_size *= 2;

    // Initialize all nodes in the tree.
    // max_p is initialized to a very small value so that "empty" leaves beyond N
    // do not affect the prefix sum calculations.
    for (int i = 0; i < MAX_NODES; ++i) {
        tree[i] = {0, -4000000000000000LL};
    }

    // Read initial transactions and place them in the segment tree leaves.
    for (int i = 0; i < N; ++i) {
        char d;
        long long b;
        cin >> d >> b;
        long long val = (d == 'R' ? b : -b);
        tree[tree_size + i] = {val, val};
    }

    // Build the segment tree from bottom to top.
    for (int i = tree_size - 1; i >= 1; --i) {
        int left = 2 * i;
        int right = 2 * i + 1;
        tree[i].sum = tree[left].sum + tree[right].sum;
        tree[i].max_p = max(tree[left].max_p, tree[left].sum + tree[right].max_p);
    }

    // Process Q queries.
    for (int q_idx = 0; q_idx < Q; ++q_idx) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: 1 p D b
            int p;
            char d;
            long long b;
            cin >> p >> d >> b;
            long long val = (d == 'R' ? b : -b);
            update(p - 1, val);
        } else if (type == 2) {
            // Search query: 2 K
            long long K;
            cin >> K;
            // tree[1].max_p is the maximum prefix sum across the entire array.
            if (tree[1].max_p < K) {
                cout << 0 << "\n";
            } else {
                // find_first returns 0-indexed position; convert to 1-indexed for output.
                cout << find_first(1, 0, tree_size - 1, 0, K) + 1 << "\n";
            }
        }
    }

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.