Overview

This problem requires performing range additions only on open stores, finalizing and recording sales when a store closes, and quickly answering “the total finalized sales of closed stores among those to the left of the \(k\)-th currently open store \(j\).”

Analysis

Key Observations

• Operation 1 performs range addition “only on open stores.” Closed stores never receive further additions.
• Operation 2 (closing) finalizes the sales at that moment (= initial value + total additions received so far) and blocks the effect of all subsequent Operation 1s.
• Operation 3 can be decomposed into two stages:
  1. Find the store number \(j\) of the \(k\)-th open store counting from the left
  2. Output the total finalized sales of “closed stores” in the range \([1, j]\)

Why a Naive Solution is Too Slow

• Directly applying Operation 1 to an array (\(O(r-l+1)\)) results in worst-case \(O(NQ)\), causing TLE.
• For each Operation 3, naively “finding the \(k\)-th open store” and “summing finalized sales of closed stores in \([1,j]\)” both tend to be linear, also causing TLE.

Solution Strategy

We need the following three capabilities: 1. Fast range addition only to open stores 2. Fast determination of the total additions received by a store (= current sales) at the time of closing 3. For Operation 3: - Fast computation of the store number \(j\) of the \(k\)-th open store - Fast computation of the prefix sum of finalized sales of closed stores (\([1,j]\))

In this solution, we use: - A segment tree (where we only accumulate lazy values without propagating them down) to manage range additions while tracking which stores are open - A BIT (Fenwick tree) managing active=¹⁄₀ to find the kth open store based on the count of open stores - A BIT that adds finalized closing sales and computes prefix sums for the prefix sum of finalized sales of closed stores

Algorithm

Below, store numbers are \(1..N\), and internally we also use 0-indexing where convenient.

1) Range Addition Only to Open Stores (Segment Tree + cnt + lazy)

Each node of the segment tree holds: - cnt[node]: The number of open stores in that interval - lazy[node]: The “accumulated sales increment added in bulk” to that interval (never pushed down to children)

Operation 1 1 l r x (1-indexed) is processed as the interval \([l-1, r)\) (0-indexed half-open interval): - If the node interval does not intersect the update interval → skip - If cnt[node]==0 (all stores in this interval are closed) → skip (this realizes “not adding to closed stores”) - If the node interval is completely contained in the update interval → lazy[node] += x - Otherwise → recurse into children

This allows us to skip entirely closed intervals and apply additions only to open stores.

2) Finalizing Current Sales at Closing Time (Sum of lazy from root to leaf)

When closing store \(p\) with Operation 2 2 p, the sales at that moment are: $\( V_p + (\text{sum of } lazy \text{ values from root to the leaf of this store}) \)$

In this implementation, instead of pushing lazy down, at closing time we: - Traverse from the leaf (store \(p\)) up to the root, summing lazy values to obtain the total additions received (\(O(\log N)\)) - Record this value as the finalized sales

Then for the closing process: - Set cnt=0 for the corresponding leaf in the segment tree, and update cnt up to the parent (making it skippable in future Operation 1s) - Subtract -1 from the “active management BIT” (setting active to 0) - Add the finalized sales to the “closed sales BIT” (placing the value at that store’s position)

3) Operation 3: Find the \(k\)-th Open Store Number \(j\) and Answer the Prefix Sum of Closed Sales

Operation 3 3 k consists of two steps:

(A) Find the store number \(j\) of the \(k\)-th open store

Prepare a BIT bit_active representing open stores, initially all 1. When a store closes, subtract 1 at that position to make it 0.

The BIT has a kth(k) function that performs a binary search-like operation to find “the first position where the prefix sum reaches \(k\) or more,” giving us: $\( j = \text{kth}(k) \)$ (1-indexed).

(B) Output the total finalized sales of closed stores in \([1, j]\)

If we add the finalized sales of closed store \(p\) to position \(p\) of bit_closed, the desired value is simply: $\( \text{bit\_closed.sum}(j) \)$ (which is 0 if there are no closed stores in the range).

Concrete Example (Illustration)

• Operation 1: “+10 to open stores in range 2–4”
• Store 3 closes → At that moment, collect the “total lazy accumulated by store 3” from root to leaf to finalize current sales, then bit_closed[3] += finalized sales
• Afterwards, even if store 3 is included in the range of an Operation 1 update, the segment tree’s cnt causes the store 3 portion to be skipped and not added to
• For Operation 3, obtain the position \(j\) of the \(k\)-th open store with bit_active.kth(k), then output bit_closed.sum(j)

Complexity

• Time complexity: \(O(Q \log N)\)
  (Operation 1’s range addition, Operation 2’s root-to-leaf sum + BIT updates, and Operation 3’s kth + prefix sum are all \(O(\log N)\))
• Space complexity: \(O(N)\)
  (Segment tree arrays cnt, lazy and 2 BITs)

Implementation Notes

• Instead of pushing lazy down, we “sum lazy from leaf to root” at closing time to determine the current value. Since Operation 3 does not require individual store values, this strategy is efficient.

• To “not add to closed stores” in Operation 1, we maintain the open store count cnt for each segment tree interval and terminate the update traversal entirely for intervals where cnt==0.

• Finding the “\(k\)-th open store” in Operation 3 is a standard technique using the BIT’s kth (recovering position from prefix sums).

• Be careful as indices are mixed:

  • BIT uses 1-indexing

  • Segment tree range updates are processed as 0-indexed half-open intervals \([l,r)\).

    Source Code

import sys


class BIT:
    __slots__ = ("n", "bit")

    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)

    def build_ones(self):
        n = self.n
        bit = self.bit
        for i in range(1, n + 1):
            bit[i] += 1
            j = i + (i & -i)
            if j <= n:
                bit[j] += bit[i]

    def add(self, i: int, delta: int):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += delta
            i += i & -i

    def sum(self, i: int) -> int:
        res = 0
        bit = self.bit
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    def kth(self, k: int) -> int:
        idx = 0
        bit = self.bit
        n = self.n
        step = 1 << (n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= n and bit[nxt] < k:
                idx = nxt
                k -= bit[nxt]
            step >>= 1
        return idx + 1


def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))
    V = [int(next(it)) for _ in range(N)]

    size = 1
    while size < N:
        size <<= 1

    cnt = [0] * (2 * size)
    lazy = [0] * (2 * size)
    base = size
    for i in range(N):
        cnt[base + i] = 1
    for i in range(base - 1, 0, -1):
        cnt[i] = cnt[i << 1] + cnt[i << 1 | 1]

    bit_active = BIT(N)
    bit_active.build_ones()
    bit_closed = BIT(N)

    def range_add(a: int, b: int, x: int):
        stack = [(1, 0, size)]
        while stack:
            idx, l, r = stack.pop()
            if b <= l or r <= a or cnt[idx] == 0:
                continue
            if a <= l and r <= b:
                lazy[idx] += x
                continue
            m = (l + r) >> 1
            stack.append((idx << 1 | 1, m, r))
            stack.append((idx << 1, l, m))

    out = []
    for _ in range(Q):
        t = int(next(it))
        if t == 1:
            l = int(next(it)) - 1
            r = int(next(it))
            x = int(next(it))
            range_add(l, r, x)
        elif t == 2:
            p = int(next(it))
            pos = p - 1
            idx = base + pos
            s = 0
            u = idx
            while u:
                s += lazy[u]
                u >>= 1
            val = V[pos] + s
            bit_closed.add(p, val)
            bit_active.add(p, -1)

            cnt[idx] = 0
            idx >>= 1
            while idx:
                cnt[idx] = cnt[idx << 1] + cnt[idx << 1 | 1]
                idx >>= 1
        else:
            k = int(next(it))
            j = bit_active.kth(k)
            out.append(str(bit_closed.sum(j)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.