概要

営業中の店舗だけに区間加算を行い、閉店時の売上を確定させて記録しつつ、「左から \(k\) 番目の営業中店舗 \(j\) までにある閉店済み店舗の確定売上の合計」を高速に答える問題です。

考察

重要な観察

• 操作1は「営業中の店舗にだけ」区間加算をします。閉店した店舗は以降一切増えません。
• 操作2（閉店）では、その時点の売上（= 初期値 + それまで受けた加算の合計）を確定し、以後の操作1の影響を遮断します。
• 操作3は
  1. 営業中店舗を左から数えて \(k\) 番目の店舗番号 \(j\) を求める
  2. 区間 \([1, j]\) にある「閉店済み店舗」の確定売上合計を出力する
     という2段階の問題に分解できます。

素朴解が厳しい理由

• 操作1をそのまま配列に反映（\(O(r-l+1)\)）すると最悪 \(O(NQ)\) でTLE。
• 操作3のたびに「\(k\) 番目の営業中店舗を探す」「\([1,j]\) の閉店済み店舗の売上を足す」を素直にやると、どちらも線形になりがちでTLE。

解決方針

必要なのは次の3つです。 1. 営業中店舗だけへの区間加算を高速に行う 2. 閉店時に その店舗が受けた加算総量（= 現在売上） を高速に確定する 3. 操作3で
- \(k\) 番目の営業中店舗番号 \(j\) を高速に求める
- 閉店済み店舗の確定売上の prefix sum（\([1,j]\)） を高速に求める

本解法では、 - 「営業中かどうか」を管理しつつ区間加算するために セグメント木（ただし値の伝播はせず lazy を積むだけ） - 「営業中店舗の個数」から \(k\) 番目を求めるために BIT（Fenwick木）で active=¹⁄₀ を管理して kth を求める - 「閉店済み店舗の確定売上の prefix sum」を求めるために BIT で閉店売上を加算して prefix sum を使います。

アルゴリズム

以下、店舗番号は \(1..N\)、内部では都合により0-indexも併用します。

1) 営業中店舗だけに区間加算する（セグ木 + cnt + lazy）

セグメント木の各ノードに - cnt[node]：その区間内にある営業中店舗数 - lazy[node]：その区間に対して「一括で足された売上増加分」（子へは押し下げない） を持ちます。

操作1 1 l r x（1-index）を区間 \([l-1, r)\)（0-index半開区間）として処理し、 - ノード区間が更新区間と交差しない → 無視 - cnt[node]==0（その区間は全店閉店済み）→ 無視（ここが「閉店店を加算しない」を実現） - ノード区間が更新区間に完全に含まれる → lazy[node] += x - それ以外 → 子へ降りる

これにより、閉店済みの区間は丸ごとスキップでき、営業中店舗にのみ加算が当たります。

2) 閉店時にその店舗の現在売上を確定する（lazy の「根→葉の和」）

操作2 2 p で店舗 \(p\) を閉店する際、その時点の売上は [ V_p + (\text{この店舗が属するノードの } lazy \text{ を根から葉まで足した総和}) ] です。

この実装では lazy を押し下げない代わりに、閉店時に - セグ木の葉（店舗\(p\)）から親へ遡りながら lazy を合計して現在の加算総量を求めます（\(O(\log N)\)） - その値を確定売上として記録します

そして閉店処理として - セグ木で該当葉の cnt=0 にし、親へ cnt を更新（以後の操作1でスキップ可能に） - 「営業中管理BIT」から -1（activeを0に） - 「閉店売上BIT」に確定売上を加算（その店舗位置に値を入れる） を行います。

3) 操作3：\(k\) 番目の営業中店舗番号 \(j\) を求め、閉店売上の prefix sum を答える

操作3 3 k は次の2ステップです。

(A) \(k\) 番目の営業中店舗番号 \(j\) を求める

営業中店舗を表すBIT bit_active を用意し、最初は全て1。 閉店したらその位置を -1 して0にします。

BITには「累積和が初めて \(k\) 以上になる位置」を二分探索的に求める kth(k) があり、 これで [ j = \text{kth}(k) ] （1-index）が求まります。

(B) \([1, j]\) にある閉店済み店舗の確定売上合計を出力

閉店した店舗 \(p\) の確定売上を bit_closed の位置 \(p\) に加算しておけば、 求めたい値は単に [ \text{bit_closed.sum}(j) ] です（閉店済みがなければ0になります）。

具体例（イメージ）

• 操作1で「2〜4番の営業中に +10」
• 3番が閉店 → その瞬間に「3番が受け取った lazy の合計」を根から拾って現在売上を確定し、bit_closed[3] += 確定売上
• 以後、操作1の更新で区間に3番が含まれても、セグ木の cnt により3番部分はスキップされ加算されない
• 操作3で \(k\) 番目営業中の位置 \(j\) を bit_active.kth(k) で得て、bit_closed.sum(j) を出力

計算量

• 時間計算量: \(O(Q \log N)\)
  （操作1の区間加算、操作2の根→葉合計＋BIT更新、操作3のkth＋prefix sum がすべて \(O(\log N)\)）
• 空間計算量: \(O(N)\)
  （セグ木配列 cnt,lazy と BIT 2本）

実装のポイント

• lazy を押し下げない代わりに、閉店時に「葉から根へ lazy を合計」して現在値を求めています。操作3では個々の店舗の値が不要なので、この戦略が効率的です。

• 操作1で「閉店済み店舗を加算しない」ために、セグ木の各区間に 営業中店舗数 cnt を持ち、cnt==0 の区間は更新探索自体を打ち切ります。

• 操作3の「\(k\) 番目の営業中店舗」は、BITの kth（累積和から位置を復元）で求めるのが定石です。

• インデックスが混在しやすいので注意：

  • BITは 1-index

  • セグ木の区間更新は 0-index 半開区間 \([l,r)\) として処理しています。

    ソースコード

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

---

この解説は gpt-5.2-high によって生成されました。