Overview

This problem requires efficiently processing “range addition only to open stores,” “closing a store (finalizing its value),” and “querying the total finalized sales up to the \(k\)-th open store” for \(N\) stores.

Analysis

The Core Difficulty

Operation 1’s “add only to open stores” is tricky. With a standard lazy segment tree range addition, it is difficult to exclude specific elements (closed stores) from the addition.

Problem with the Naive Approach

If we naively search all open stores in \([l, r]\) for operation 1, each operation takes \(O(N)\), resulting in \(O(NQ)\) overall, which causes TLE.

Solution: Square Root Decomposition + Fenwick Tree

By using square root decomposition, we can efficiently handle operation 1’s “add only to open stores.”

• Divide stores into blocks of \(\sqrt{N}\) each
• Maintain a “block lazy value (block_lazy)” for each block
• For fully covered blocks, just add to lazy (\(O(1)\))
• For partial blocks at the edges, process individually (\(O(\sqrt{N})\))

Key point: block_lazy represents “the cumulative value to be added to all open stores within that block.” When closing a store, we compute the finalized value as base[p] + block_lazy[b], so the store is unaffected by lazy changes after closing.

For operation 3, we use two Fenwick Trees (BITs) — one to quickly find “the \(k\)-th open store” and another to compute “the total sales of closed stores” over an interval.

Algorithm

Data Structures

Structure	Purpose
base[i]	Value of store \(i\) (excluding block lazy)
block_lazy[b]	Cumulative addition value for open stores in block \(b\)
open_bit	BIT for the count of open stores (for finding the \(k\)-th)
frozen_bit	BIT for finalized values (for range sum queries)

Processing Each Operation

Operation 1 (1 l r x): - Fully covered blocks: block_lazy[b] += x - Partial blocks at edges: only add base[i] += x for open stores

Operation 2 (2 p): - Finalized value = base[p] + block_lazy[block of p] - Add the finalized value to frozen_bit - Subtract 1 from open_bit - Update is_open[p] = False

Operation 3 (3 k): - Binary search on open_bit to find position \(j\) of the \(k\)-th open store - Query frozen_bit for the sum over \([1, j]\) and output it

Complexity

• Time complexity: \(O((N + Q) \sqrt{N})\)
  • Operation 1: \(O(\sqrt{N})\) (\(O(\sqrt{N})\) full blocks, \(O(\sqrt{N})\) elements at edges)
  • Operation 2: \(O(\log N)\) (BIT updates)
  • Operation 3: \(O(\log N)\) (binary search on BIT and query)
• Space complexity: \(O(N)\)

Implementation Notes

• Finding the \(k\)-th element on a BIT: Using binary lifting, we find the minimum position where the prefix sum is at least \(k\) in \(O(\log N)\). This has a smaller constant factor than standard binary search.

• Finalizing value at closing time: We compute the current exact sales as base[p] + block_lazy[b]. This ensures that even if the block’s lazy value increases after closing, the closed store is unaffected.

• Processing partial blocks at edges: In operation 1, we check is_open[i] and only update base[i] for open stores. Closed stores are skipped, ensuring correctness.

• Output optimization: Results are accumulated in a list and printed all at once at the end, reducing I/O overhead.

  Source Code

import sys
from sys import stdin

def main():
    input = stdin.readline
    
    N, Q = map(int, stdin.readline().split())
    V = list(map(int, stdin.readline().split()))
    
    # We need:
    # 1. Range add on open shops only
    # 2. Close a shop (freeze its value)
    # 3. Find k-th open shop, then sum frozen values of closed shops in [1..j]
    
    # Key insight: Use a "global add" approach with timestamps.
    # For each shop, track its value as V[i] + (sum of all x's from operation 1 that apply to it while open).
    # 
    # Alternative approach using sqrt decomposition:
    # 
    # Actually, let me think about this differently.
    # 
    # For operation 1: range add x to open shops in [l,r]
    # For operation 2: close shop p, freeze its current value
    # For operation 3: find k-th open shop (position j), sum of frozen values in [1..j]
    #
    # We can use a BIT (Fenwick tree) for open shops to find k-th open shop.
    # For the frozen values prefix sum, we can use another BIT.
    # The hard part is operation 1: range add to open shops only.
    #
    # Sqrt decomposition approach:
    # Divide shops into blocks of size ~sqrt(N).
    # Each block maintains:
    #   - count of open shops
    #   - a lazy add value for open shops in the block
    #   - for each shop, its "base" value (without block lazy)
    #   - sum of frozen values (prefix-queryable)
    #
    # For op 1 [l,r,x]: for full blocks, add x to block lazy (only affects open shops when evaluated)
    #   For partial blocks, manually update open shops.
    # For op 2 p: freeze shop p's value = base[p] + block_lazy, set it as frozen. Update open count.
    # For op 3 k: find k-th open shop using block open counts, then sum frozen values up to position j.
    
    B = max(1, int(N**0.5))  # block size
    num_blocks = (N + B - 1) // B
    
    base = V[:]  # current base value for each shop (without block lazy)
    is_open = [True] * N
    frozen_val = [0] * N  # frozen value when closed
    
    block_lazy = [0] * num_blocks
    block_open_count = [0] * num_blocks
    # prefix sum of frozen values: use a BIT
    # BIT for frozen values
    frozen_bit = [0] * (N + 1)
    # BIT for open count
    open_bit = [0] * (N + 1)
    
    def bit_update(bit, i, delta):
        i += 1
        while i <= N:
            bit[i] += delta
            i += i & (-i)
    
    def bit_query(bit, i):
        s = 0
        i += 1
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    def bit_kth(bit, k):
        # find smallest i such that prefix sum [0..i] >= k (1-indexed k)
        pos = 0
        r = 1
        while r <= N:
            r <<= 1
        r >>= 1
        while r > 0:
            if pos + r <= N and bit[pos + r] < k:
                k -= bit[pos + r]
                pos += r
            r >>= 1
        return pos  # 0-indexed
    
    for i in range(N):
        block_open_count[i // B] += 1
        bit_update(open_bit, i, 1)
    
    out = []
    
    for _ in range(Q):
        line = stdin.readline().split()
        op = line[0]
        
        if op == '1':
            l, r, x = int(line[1]) - 1, int(line[2]) - 1, int(line[3])
            lb = l // B
            rb = r // B
            if lb == rb:
                for i in range(l, r + 1):
                    if is_open[i]:
                        base[i] += x
            else:
                # left partial
                for i in range(l, (lb + 1) * B):
                    if is_open[i]:
                        base[i] += x
                # full blocks
                for b in range(lb + 1, rb):
                    block_lazy[b] += x
                # right partial
                for i in range(rb * B, r + 1):
                    if is_open[i]:
                        base[i] += x
        
        elif op == '2':
            p = int(line[1]) - 1
            b = p // B
            fv = base[p] + block_lazy[b]
            frozen_val[p] = fv
            is_open[p] = False
            block_open_count[b] -= 1
            bit_update(open_bit, p, -1)
            bit_update(frozen_bit, p, fv)
        
        else:  # op == '3'
            k = int(line[1])
            j = bit_kth(open_bit, k)  # 0-indexed position of k-th open shop
            # sum of frozen values in [0..j]
            ans = bit_query(frozen_bit, j)
            out.append(ans)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n' if out else '')

main()

---

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