Overview

This problem requires efficiently processing three types of queries: adding books to a specific range of shelves (range addition), removing all books from a specific shelf (point clear), and finding the total number of books in a specific range (range sum query).

Analysis

Naive Approach

Consider managing the number of books on each shelf using a regular array. - Task 1 (Range Addition): Add \(1\) to elements from the \(l\)-th to the \(r\)-th in the array. Worst case \(O(N)\). - Task 2 (Point Clear): Set the \(p\)-th element to \(0\). \(O(1)\). - Task 3 (Range Sum Query): Compute the sum from the \(l\)-th to the \(r\)-th element using a loop. Worst case \(O(N)\).

With this approach, each operation takes up to \(O(N)\) time. Since the number of operations \(Q\) can also be up to \(2 \times 10^5\), the overall time complexity is \(O(NQ)\), which will not meet the time limit (resulting in TLE).

Ideas for Optimization

A representative data structure for efficiently performing range addition and range sum queries is the Lazy Segment Tree. Using a lazy segment tree, both range addition and range sum queries can be performed in \(O(\log N)\) each.

However, this problem includes the operation “Task 2: Set the value at a specific position \(p\) to \(0\)”. Since a standard lazy segment tree only supports range addition, the key challenge is how to handle this “point clear” operation.

Solution for Point Clear

In a segment tree, to overwrite the value at a specific point \(p\), all pending addition operations (lazy values) affecting that position must be resolved (propagated).

Specifically, the point clear can be achieved in \(O(\log N)\) by following these steps: 1. Propagate lazy values (Top-down): Starting from the root toward the leaf (position \(p\)), push down the lazy values of nodes along the path from the root to \(p\) to their child nodes. This ensures that the value at leaf \(p\) becomes the correct up-to-date value. 2. Overwrite the value: Change the value at leaf \(p\) to \(0\). 3. Recompute range sums (Bottom-up): From the modified leaf \(p\) back up to the root, update each parent node’s value as “left child’s value + right child’s value”.

This allows the point clear to be performed correctly while maintaining the consistency of the lazy segment tree.

---

Algorithm

Using a lazy segment tree, each query is processed as follows.

1. Segment Tree Construction

For each node, the following information is maintained: - tree_val[i]: The current total number of books in the range represented by node \(i\). - tree_len[i]: The length (number of shelves) of the range covered by node \(i\). This is used to multiply the added value by this length and add it to the range sum during range addition. - lazy[i]: The pending lazy addition value stored at node \(i\).

2. Processing Each Query

• Task 1 (Range Addition): Perform the standard lazy segment tree range addition on the interval \([l, r)\). Add the lazy value lazy to the necessary nodes and update the range sum tree_val.
• Task 2 (Point Clear):
  1. Push and propagate the lazy values of nodes along the path from the root to leaf \(p\), from top to bottom.
  2. Set the tree_val of the node corresponding to leaf \(p\) to \(0\).
  3. From leaf \(p\) back up to the root, recompute each parent node’s value as “left child + right child”.
• Task 3 (Range Sum Query): Perform the standard lazy segment tree range sum query on the interval \([l, r)\). Propagate lazy values as needed while accumulating and returning the sum of the relevant ranges.

---

Complexity

• Time Complexity:

  • Segment tree initialization: \(O(N)\)
  • Processing each query (Tasks 1, 2, 3): All \(O(\log N)\)
  • Overall time complexity: \(O(N + Q \log N)\) This is well within the time limit (typically 2.0 seconds) under the constraints \(N, Q \le 2 \times 10^5\).

• Space Complexity:

  • Let \(M\) be the smallest power of \(2\) that is at least \(N\). Several arrays of size \(2M\) are needed for the segment tree.
  • Overall space complexity: \(O(N)\) This comfortably fits within the memory limit.

---

Implementation Notes

• Converting between 1-based and 0-based indexing: The problem gives shelf numbers from \(1\) to \(N\) (1-based), but internally the program processes them from \(0\) to \(N-1\) (0-based). Therefore, \(1\) is subtracted from the input values \(l\) and \(p\) (the right endpoint \(r\) is used as-is since the interval is treated as the half-open interval \([l, r)\)).

• Optimization using bit operations: Moving to a parent node (i >>= 1) and moving to child nodes (2 * i or 2 * i + 1) are done using bit operations, enabling faster execution even in Python.

• Utilizing tree_len: When adding \(x\) to a range, the range sum increases by “(length of the range) \(\times x\)”. By precomputing the length of the range each node covers in the tree_len array, the computations during push and range addition can be done in \(O(1)\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    size = 1
    log = 0
    while size < N:
        size <<= 1
        log += 1
        
    tree_val = [0] * (2 * size)
    tree_len = [0] * (2 * size)
    lazy = [0] * size
    
    for i in range(N):
        tree_len[size + i] = 1
    for i in range(size - 1, 0, -1):
        tree_len[i] = tree_len[2 * i] + tree_len[2 * i + 1]
        
    def push(k):
        f = lazy[k]
        if f != 0:
            lk = 2 * k
            tree_val[lk] += f * tree_len[lk]
            if lk < size:
                lazy[lk] += f
            rk = lk + 1
            tree_val[rk] += f * tree_len[rk]
            if rk < size:
                lazy[rk] += f
            lazy[k] = 0

    def point_clear(p):
        g = p + size
        for i in range(log, 0, -1):
            push(g >> i)
        tree_val[g] = 0
        g >>= 1
        while g > 0:
            tree_val[g] = tree_val[2 * g] + tree_val[2 * g + 1]
            g >>= 1

    def range_add(l, r, x):
        if l >= r:
            return
        l += size
        r += size
        
        for i in range(log, 0, -1):
            mask = (1 << i) - 1
            if l & mask:
                push(l >> i)
            if r & mask:
                push((r - 1) >> i)
                
        l_opt, r_opt = l, r
        while l < r:
            if l & 1:
                tree_val[l] += x * tree_len[l]
                if l < size:
                    lazy[l] += x
                l += 1
            if r & 1:
                r -= 1
                tree_val[r] += x * tree_len[r]
                if r < size:
                    lazy[r] += x
            l >>= 1
            r >>= 1
            
        l, r = l_opt, r_opt
        for i in range(1, log + 1):
            mask = (1 << i) - 1
            if l & mask:
                p = l >> i
                tree_val[p] = tree_val[2 * p] + tree_val[2 * p + 1]
            if r & mask:
                p = (r - 1) >> i
                tree_val[p] = tree_val[2 * p] + tree_val[2 * p + 1]

    def range_sum(l, r):
        if l >= r:
            return 0
        l += size
        r += size
        
        for i in range(log, 0, -1):
            mask = (1 << i) - 1
            if l & mask:
                push(l >> i)
            if r & mask:
                push((r - 1) >> i)
                
        res = 0
        while l < r:
            if l & 1:
                res += tree_val[l]
                l += 1
            if r & 1:
                r -= 1
                res += tree_val[r]
            l >>= 1
            r >>= 1
        return res

    out = []
    idx = 2
    len_data = len(input_data)
    while idx < len_data:
        t = input_data[idx]
        if t == '1':
            l = int(input_data[idx+1]) - 1
            r = int(input_data[idx+2])
            range_add(l, r, 1)
            idx += 3
        elif t == '2':
            p = int(input_data[idx+1]) - 1
            point_clear(p)
            idx += 2
        else:
            l = int(input_data[idx+1]) - 1
            r = int(input_data[idx+2])
            out.append(str(range_sum(l, r)))
            idx += 3
            
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

---

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