Overview

This problem requires efficiently processing three types of operations on \(N\) shelves arranged in a row: “add one book to each shelf in an interval,” “reset a single shelf to zero books,” and “find the total number of books in an interval.”

Analysis

Problems with the Naive Approach

If we manage the number of books on each shelf using an array: - Operation 1 (range addition): Takes \(O(r - l + 1)\), worst case \(O(N)\) - Operation 3 (range sum): Takes \(O(r - l + 1)\), worst case \(O(N)\)

Since \(N, Q\) are at most \(2 \times 10^5\), the total \(O(NQ)\) is at most \(4 \times 10^{10}\), which will TLE.

Key Insight

We separate each shelf’s value into an “addition component” and an “adjustment component” for management.

• \(\text{add}[i]\) = cumulative number of times shelf \(i\) has been included in Operation 1
• \(\text{adj}[i]\) = adjustment value for shelf \(i\) (used for reset operations)

Then, the actual number of books on shelf \(i\) can be expressed as \(\text{add}[i] + \text{adj}[i]\).

Processing Each Operation

• Operation 1 \((l, r)\): Add \(+1\) uniformly to \(\text{add}[l..r]\) (range addition)
• Operation 2 \((p)\): To set the actual book count to \(0\), update \(\text{adj}[p] = -\text{add}[p]\) (point update)
• Operation 3 \((l, r)\): Compute \(\sum_{i=l}^{r}(\text{add}[i] + \text{adj}[i])\) (range sum)

This allows us to use data structures suited to each component.

Algorithm

Efficient Processing Using BIT (Fenwick Tree)

add component: Range addition + Range sum query

Using two BITs (\(B_1, B_2\)), we achieve range addition and range sum with the following formula:

\[\text{prefix\_sum}(x) = B_1[x] \times x - B_2[x]\]

When adding \(+1\) to the interval \([l, r]\): - In \(B_1\): add \(+1\) at \(l\), add \(-1\) at \(r+1\) - In \(B_2\): add \(+(l-1)\) at \(l\), add \(-r\) at \(r+1\)

adj component: Point update + Range sum query

Managed with a single standard BIT (\(B_3\)). When updating \(\text{adj}[p]\) in Operation 2, we compute the difference \(\Delta = \text{new adj}[p] - \text{old adj}[p]\) and apply it to the BIT. The current value of \(\text{adj}[p]\) is stored in a separate array adj_val.

Concrete Example

With 5 shelves, performing Operation 1 \((1, 3)\), Operation 1 \((2, 4)\), Operation 2 \((2)\), Operation 3 \((1, 4)\):

1. After Operation 1: \(\text{add} = [1, 1, 1, 0, 0]\)
2. After Operation 1: \(\text{add} = [1, 2, 2, 1, 0]\)
3. Operation 2: \(\text{add}[2] = 2\), so set \(\text{adj}[2] = -2\)
4. Operation 3: \((1+0) + (2+(-2)) + (2+0) + (1+0) = 1 + 0 + 2 + 1 = 4\)

Complexity

• Time complexity: \(O(Q \log N)\) (each operation calls BIT a constant number of times, and each BIT operation is \(O(\log N)\))
• Space complexity: \(O(N)\) (three BITs and the adjustment value array)

Implementation Notes

• Point query for add: In Operation 2, we need to know the cumulative addition for shelf \(p\), so we compute it as \(\text{prefix\_sum}(p) - \text{prefix\_sum}(p-1)\).

• Difference management for adj: Since a BIT is a data structure that cumulatively adds values, to “set” \(\text{adj}[p]\) to a new value, we add the difference from the old value to the BIT. This is why the auxiliary array adj_val is needed.

• Fast input reading: In Python, we use sys.stdin.buffer.read() and batch the output for faster I/O.

  Source Code

import sys
from math import sqrt

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    # sqrt decomposition approach
    # Each position has a value = (number of type-1 additions that cover it) - (adjustments from type-2 resets)
    # 
    # We maintain:
    # - A BIT (Fenwick tree) for range-add (type 1) using difference array technique
    #   This tracks the cumulative additions from type 1 operations.
    # - For type 2 (reset at position p), we need to know current value at p and subtract it.
    #   We can handle this by maintaining a separate "adjustment" array.
    #
    # Actually, let me think more carefully.
    #
    # Let add[i] = total number of type-1 operations that include position i (cumulative).
    # Let adj[i] = adjustment value for position i (starts at 0).
    # The actual value at position i = add[i] + adj[i].
    #
    # Type 1 (l, r): increment add[i] for all i in [l, r] by 1. (Range add)
    # Type 2 (p): set adj[p] = -add[p] (so that actual value becomes 0). But adj[p] was something before.
    #   Actually: current value = add[p] + adj[p]. We want it to become 0, so adj[p] = -add[p].
    # Type 3 (l, r): sum of (add[i] + adj[i]) for i in [l, r] = sum(add[l..r]) + sum(adj[l..r]).
    #
    # For add: we need range add and range sum. Use a BIT with range update/range query.
    # For adj: we need point update and range sum. Use a simple BIT.
    
    # BIT for range add, range sum (add array)
    # Using two BITs B1, B2 such that prefix_sum(x) = B1[x]*x - B2[x]
    B1 = [0] * (N + 2)
    B2 = [0] * (N + 2)
    
    def bit_update(bit, i, delta):
        while i <= N:
            bit[i] += delta
            i += i & (-i)
    
    def bit_query(bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    def range_add(l, r, val):
        bit_update(B1, l, val)
        bit_update(B1, r + 1, -val)
        bit_update(B2, l, val * (l - 1))
        bit_update(B2, r + 1, -val * r)
    
    def prefix_sum_add(x):
        return bit_query(B1, x) * x - bit_query(B2, x)
    
    def range_sum_add(l, r):
        return prefix_sum_add(r) - prefix_sum_add(l - 1)
    
    # BIT for adj array (point update, range sum)
    B3 = [0] * (N + 2)
    
    def adj_update(i, delta):
        while i <= N:
            B3[i] += delta
            i += i & (-i)
    
    def adj_prefix_sum(i):
        s = 0
        while i > 0:
            s += B3[i]
            i -= i & (-i)
        return s
    
    def adj_range_sum(l, r):
        return adj_prefix_sum(r) - adj_prefix_sum(l - 1)
    
    # adj_val[i] stores the current adjustment for position i
    adj_val = [0] * (N + 1)
    
    out = []
    
    for _ in range(Q):
        t = int(input_data[idx]); idx += 1
        if t == 1:
            l = int(input_data[idx]); idx += 1
            r = int(input_data[idx]); idx += 1
            range_add(l, r, 1)
        elif t == 2:
            p = int(input_data[idx]); idx += 1
            # current value at p = add[p] + adj_val[p], we want it to be 0
            add_p = prefix_sum_add(p) - prefix_sum_add(p - 1)
            new_adj = -add_p
            delta = new_adj - adj_val[p]
            adj_val[p] = new_adj
            adj_update(p, delta)
        else:
            l = int(input_data[idx]); idx += 1
            r = int(input_data[idx]); idx += 1
            ans = range_sum_add(l, r) + adj_range_sum(l, r)
            out.append(ans)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

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