概要

\(N\) 軒の店舗に対し、「営業中の店舗のみへの範囲加算」「店舗の閉店（値の確定）」「\(k\) 番目の営業中店舗までの閉店済み売上合計の問い合わせ」を効率的に処理する問題です。

考察

難しさの本質

操作 1 の「営業中の店舗のみに加算する」が厄介です。通常の遅延セグメント木による範囲加算では、特定の要素（閉店済み店舗）を除外して加算することが困難です。

素朴なアプローチの問題

愚直に操作 1 で \([l, r]\) 内の営業中店舗を全探索すると、1回の操作で \(O(N)\) かかり、全体で \(O(NQ)\) となって TLE します。

解決策：平方分割 + Fenwick Tree

平方分割を使うことで、操作 1 の「営業中の店舗のみへの加算」を効率化できます。

• 店舗を \(\sqrt{N}\) 個ずつのブロックに分割する
• 各ブロックに「ブロック遅延値（block_lazy）」を持たせる
• 完全にカバーされるブロックには lazy を加算するだけ（\(O(1)\)）
• 端のブロックは個別に処理（\(O(\sqrt{N})\)）

ポイント：block_lazy は「そのブロック内の営業中の店舗すべてに加算される累積値」を表します。閉店時に base[p] + block_lazy[b] で確定値を計算すれば、閉店後は lazy の影響を受けません。

操作 3 では「\(k\) 番目の営業中店舗」を高速に見つけるため、また「閉店済み店舗の売上合計」を区間で求めるために、Fenwick Tree（BIT） を2本使います。

アルゴリズム

データ構造

構造	用途
base[i]	店舗 \(i\) の値（ブロック遅延を含まない部分）
block_lazy[b]	ブロック \(b\) 内の営業中店舗への累積加算値
open_bit	営業中店舗数の BIT（\(k\) 番目の検索用）
frozen_bit	閉店確定値の BIT（区間合計クエリ用）

各操作の処理

操作 1（1 l r x）： - 完全にカバーされるブロック：block_lazy[b] += x - 端のブロック：営業中の店舗のみ base[i] += x

操作 2（2 p）： - 確定値 = base[p] + block_lazy[p のブロック] - frozen_bit に確定値を加算 - open_bit から 1 を減算 - is_open[p] = False に更新

操作 3（3 k）： - open_bit 上で二分探索し、\(k\) 番目の営業中店舗の位置 \(j\) を求める - frozen_bit で \([1, j]\) の合計を求めて出力

計算量

• 時間計算量: \(O((N + Q) \sqrt{N})\)
  • 操作 1：\(O(\sqrt{N})\)（完全ブロックは \(O(\sqrt{N})\) 個、端は \(O(\sqrt{N})\) 要素）
  • 操作 2：\(O(\log N)\)（BIT の更新）
  • 操作 3：\(O(\log N)\)（BIT 上の二分探索とクエリ）
• 空間計算量: \(O(N)\)

実装のポイント

• BIT 上の \(k\) 番目検索：二分探索（binary lifting）を使い、累積和が \(k\) 以上になる最小位置を \(O(\log N)\) で求めます。通常の二分探索より定数倍が軽いです。

• 閉店時の値の確定：base[p] + block_lazy[b] で現在の正確な売上を計算します。これにより、閉店後にブロックの lazy が増えても影響を受けません。

• 端ブロックの処理：操作 1 で is_open[i] を確認し、営業中の店舗のみ base[i] を更新します。閉店済み店舗はスキップされるため正しく動作します。

• 出力の高速化：結果をリストに溜めて最後に一括出力することで、I/O のオーバーヘッドを軽減しています。

  ソースコード

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()

---

この解説は claude4.6opus-thinking によって生成されました。