概要

横一列に並んだ \(N\) 個の棚に対して、「区間に1冊ずつ追加」「1つの棚を0冊にリセット」「区間の合計を求める」の3種類の操作を効率的に処理する問題です。

考察

素朴なアプローチの問題点

各棚の冊数を配列で管理する場合： - 作業1（区間加算）：\(O(r - l + 1)\) かかり、最悪 \(O(N)\) - 作業3（区間和）：\(O(r - l + 1)\) かかり、最悪 \(O(N)\)

\(N, Q\) が最大 \(2 \times 10^5\) なので、合計 \(O(NQ)\) は最大 \(4 \times 10^{10}\) となりTLEします。

重要な気づき

各棚の値を「加算成分」と「調整成分」に分離して管理します。

• \(\text{add}[i]\) = 棚 \(i\) を含むすべての作業1による累積加算回数
• \(\text{adj}[i]\) = 棚 \(i\) に対する調整値（リセット操作で使用）

すると、棚 \(i\) の実際の冊数は \(\text{add}[i] + \text{adj}[i]\) と表せます。

各操作の処理

• 作業1 \((l, r)\)：\(\text{add}[l..r]\) に一律 \(+1\)（区間加算）
• 作業2 \((p)\)：実際の冊数を \(0\) にしたいので、\(\text{adj}[p] = -\text{add}[p]\) に更新（点更新）
• 作業3 \((l, r)\)：\(\sum_{i=l}^{r}(\text{add}[i] + \text{adj}[i])\) を計算（区間和）

これにより、各成分に適したデータ構造を使い分けられます。

アルゴリズム

BIT（Fenwick Tree）を用いた高速処理

add 成分：区間加算 + 区間和クエリ

2本のBIT（\(B_1, B_2\)）を使い、以下の公式で区間加算・区間和を実現します：

\[\text{prefix\_sum}(x) = B_1[x] \times x - B_2[x]\]

区間 \([l, r]\) に \(+1\) する際： - \(B_1\) に \(l\) で \(+1\)、\(r+1\) で \(-1\) - \(B_2\) に \(l\) で \(+(l-1)\)、\(r+1\) で \(-r\)

adj 成分：点更新 + 区間和クエリ

通常の1本のBIT（\(B_3\)）で管理します。作業2で \(\text{adj}[p]\) を更新する際、差分 \(\Delta = \text{新しい adj}[p] - \text{古い adj}[p]\) を計算し、BITに反映します。現在の \(\text{adj}[p]\) の値は別の配列 adj_val に保持します。

具体例

棚が5個で、作業1 \((1, 3)\)、作業1 \((2, 4)\)、作業2 \((2)\)、作業3 \((1, 4)\) の場合：

1. 作業1後：\(\text{add} = [1, 1, 1, 0, 0]\)
2. 作業1後：\(\text{add} = [1, 2, 2, 1, 0]\)
3. 作業2：\(\text{add}[2] = 2\) なので \(\text{adj}[2] = -2\) に設定
4. 作業3：\((1+0) + (2+(-2)) + (2+0) + (1+0) = 1 + 0 + 2 + 1 = 4\)

計算量

• 時間計算量: \(O(Q \log N)\)（各操作で BIT を定数回呼び出し、各 BIT 操作は \(O(\log N)\)）
• 空間計算量: \(O(N)\)（BIT 3本と調整値配列）

実装のポイント

• add の点クエリ：作業2で棚 \(p\) の加算累積を知る必要があるため、\(\text{prefix\_sum}(p) - \text{prefix\_sum}(p-1)\) で計算します。

• adj の差分管理：BIT は累積的に加算するデータ構造なので、\(\text{adj}[p]\) を新しい値に「設定」するには、古い値との差分をBITに加えます。そのため補助配列 adj_val が必要です。

• 入力の高速読み込み：Python では sys.stdin.buffer.read() を使い、出力もまとめて行うことで高速化しています。

  ソースコード

import sys
from math import sqrt

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    # sqrt decomposition approach
    # Each position has a value = (number of type-1 additions that cover it) - (adjustments from type-2 resets)
    # 
    # We maintain:
    # - A BIT (Fenwick tree) for range-add (type 1) using difference array technique
    #   This tracks the cumulative additions from type 1 operations.
    # - For type 2 (reset at position p), we need to know current value at p and subtract it.
    #   We can handle this by maintaining a separate "adjustment" array.
    #
    # Actually, let me think more carefully.
    #
    # Let add[i] = total number of type-1 operations that include position i (cumulative).
    # Let adj[i] = adjustment value for position i (starts at 0).
    # The actual value at position i = add[i] + adj[i].
    #
    # Type 1 (l, r): increment add[i] for all i in [l, r] by 1. (Range add)
    # Type 2 (p): set adj[p] = -add[p] (so that actual value becomes 0). But adj[p] was something before.
    #   Actually: current value = add[p] + adj[p]. We want it to become 0, so adj[p] = -add[p].
    # Type 3 (l, r): sum of (add[i] + adj[i]) for i in [l, r] = sum(add[l..r]) + sum(adj[l..r]).
    #
    # For add: we need range add and range sum. Use a BIT with range update/range query.
    # For adj: we need point update and range sum. Use a simple BIT.
    
    # BIT for range add, range sum (add array)
    # Using two BITs B1, B2 such that prefix_sum(x) = B1[x]*x - B2[x]
    B1 = [0] * (N + 2)
    B2 = [0] * (N + 2)
    
    def bit_update(bit, i, delta):
        while i <= N:
            bit[i] += delta
            i += i & (-i)
    
    def bit_query(bit, i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s
    
    def range_add(l, r, val):
        bit_update(B1, l, val)
        bit_update(B1, r + 1, -val)
        bit_update(B2, l, val * (l - 1))
        bit_update(B2, r + 1, -val * r)
    
    def prefix_sum_add(x):
        return bit_query(B1, x) * x - bit_query(B2, x)
    
    def range_sum_add(l, r):
        return prefix_sum_add(r) - prefix_sum_add(l - 1)
    
    # BIT for adj array (point update, range sum)
    B3 = [0] * (N + 2)
    
    def adj_update(i, delta):
        while i <= N:
            B3[i] += delta
            i += i & (-i)
    
    def adj_prefix_sum(i):
        s = 0
        while i > 0:
            s += B3[i]
            i -= i & (-i)
        return s
    
    def adj_range_sum(l, r):
        return adj_prefix_sum(r) - adj_prefix_sum(l - 1)
    
    # adj_val[i] stores the current adjustment for position i
    adj_val = [0] * (N + 1)
    
    out = []
    
    for _ in range(Q):
        t = int(input_data[idx]); idx += 1
        if t == 1:
            l = int(input_data[idx]); idx += 1
            r = int(input_data[idx]); idx += 1
            range_add(l, r, 1)
        elif t == 2:
            p = int(input_data[idx]); idx += 1
            # current value at p = add[p] + adj_val[p], we want it to be 0
            add_p = prefix_sum_add(p) - prefix_sum_add(p - 1)
            new_adj = -add_p
            delta = new_adj - adj_val[p]
            adj_val[p] = new_adj
            adj_update(p, delta)
        else:
            l = int(input_data[idx]); idx += 1
            r = int(input_data[idx]); idx += 1
            ans = range_sum_add(l, r) + adj_range_sum(l, r)
            out.append(ans)
    
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

---

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