概要

\(N\) 個の部屋に対して \(Q\) 回の範囲トグル操作を行った後、\(M\) 個の会議室のうち点灯している部屋の数を求める問題です。

考察

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

単純に考えると、長さ \(N\) の配列を用意して各操作で範囲内の照明状態を反転させる方法が思いつきます。しかし、\(N\) が最大 \(10^9\) と非常に大きいため、配列を確保することすらできません。また、各操作で最大 \(N\) 個の要素を更新すると、時間計算量は \(O(NQ)\) となりTLEになります。

重要な気づき

1. トグル回数の偶奇が重要: ある部屋の最終的な照明状態は、その部屋が何回トグルされたかの偶奇で決まります。奇数回トグルされれば点灯、偶数回なら消灯です。

2. 調べるべき部屋は \(M\) 個だけ: 最終的に必要なのは \(M\) 個の会議室の状態だけです。\(M \leq 2 \times 10^5\) なので、各会議室について個別に判定できれば十分です。

3. いもす法の適用: 範囲 \([L, R]\) への操作は、\(L\) で \(+1\)、\(R+1\) で \(-1\) というイベントとして記録できます。累積和を取ることで、各位置でのトグル回数が分かります。

解決方針

座標圧縮の考え方を使い、イベントが発生する点（\(L\) や \(R+1\)）だけを管理します。これにより、点灯している区間のリストを効率的に構築できます。

アルゴリズム

1. イベントの作成: 各操作 \([L_i, R_i]\) に対して、位置 \(L_i\) に \(+1\)、位置 \(R_i + 1\) に \(-1\) のイベントを追加します。

2. イベントのソートと処理: イベントを位置でソートし、左から順に累積和を計算します。累積和が奇数の区間は点灯しています。

3. 点灯区間のリスト作成: 累積和が奇数になる区間 \([start, end]\) をリストに追加します。

4. 各会議室の判定: 会議室の部屋番号 \(b\) が点灯区間に含まれるかを二分探索で判定します。

具体例

\(Q = 2\) で操作が \([1, 5]\) と \([3, 7]\) の場合： - イベント: \((1, +1), (6, -1), (3, +1), (8, -1)\) - ソート後: \((1, +1), (3, +1), (6, -1), (8, -1)\) - 累積和の推移: - 位置 \(1\)〜\(2\): 累積和 \(1\)（奇数）→ 点灯 - 位置 \(3\)〜\(5\): 累積和 \(2\)（偶数）→ 消灯 - 位置 \(6\)〜\(7\): 累積和 \(1\)（奇数）→ 点灯

計算量

• 時間計算量: \(O(Q \log Q + M \log Q)\)
  • イベントのソートに \(O(Q \log Q)\)
  • 各会議室の二分探索に \(O(M \log Q)\)
• 空間計算量: \(O(Q + M)\)
  • イベントと点灯区間の保存に \(O(Q)\)
  • 会議室リストに \(O(M)\)

実装のポイント

• 区間の終端に注意: 操作 \([L, R]\) に対して、\(R+1\) の位置で \(-1\) を記録します。これにより、\(R\) までが操作の影響を受けます。

• 二分探索の使い方: 会議室 \(b\) を含む可能性があるのは、開始位置が \(b\) 以下の区間です。bisect_right(starts, b) - 1 で該当する区間のインデックスを取得し、その区間の終端が \(b\) 以上かを確認します。

• 空のイベントリストへの対処: 操作がない場合や点灯区間がない場合も正しく処理できるよう、if intervals: でガードしています。

  ソースコード

import sys
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    B = [int(input_data[idx + i]) for i in range(M)]
    idx += M
    
    operations = []
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        operations.append((L, R))
    
    # 座標圧縮のためのイベント点を収集
    # 各操作 [L, R] に対して、L で +1、R+1 で -1 のイベントを作成
    events = []
    for L, R in operations:
        events.append((L, 1))
        events.append((R + 1, -1))
    
    # イベントをソート
    events.sort()
    
    # 累積和を計算して、各区間でのトグル回数を求める
    # 結果として、トグル回数が奇数の区間が点灯している
    
    # イベント点をまとめて処理
    toggle_count = 0
    # (開始位置, 終了位置, トグル回数の偶奇) のリストを作成
    intervals = []  # (start, end) で点灯している区間
    
    prev_pos = None
    for pos, delta in events:
        if prev_pos is not None and prev_pos < pos:
            if toggle_count % 2 == 1:
                intervals.append((prev_pos, pos - 1))
        toggle_count += delta
        prev_pos = pos
    
    # 各会議室について、点灯しているかチェック
    # intervals は点灯している区間のリスト
    # 各会議室 b について、b を含む区間があるかを二分探索で調べる
    
    # intervals を開始位置でソート（すでにソートされているはず）
    # 各区間 (start, end) について、start <= b <= end なら点灯
    
    count = 0
    if intervals:
        starts = [interval[0] for interval in intervals]
        
        for b in B:
            # b 以下の最大の start を持つ区間を探す
            idx_interval = bisect_right(starts, b) - 1
            if idx_interval >= 0:
                start, end = intervals[idx_interval]
                if start <= b <= end:
                    count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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