概要

花壇の区間 \([L, R]\) に含まれる異なる花の品種数を、複数のクエリに対して効率的に求める問題です。Mo’s algorithm（平方分割）を用いて解きます。

考察

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

各クエリごとに区間 \([L, R]\) を走査して品種数を数えると、1回のクエリに \(O(N)\) かかります。\(Q\) 個のクエリがあるので、全体で \(O(NQ)\) となり、\(N, Q\) が最大 \(10^5\) のとき \(10^{10}\) 回の操作が必要になり、TLE（時間制限超過）になります。

重要な気づき

• 区間の端を1つ動かす操作（要素を1つ追加/削除）は \(O(1)\) でできます
• クエリをうまく並べ替えれば、区間の端の移動回数を減らせます
• これは Mo’s algorithm が有効な典型的な問題パターンです

アルゴリズム

Mo’s algorithm の概要

Mo’s algorithm は、区間クエリを効率的に処理するためのオフラインアルゴリズムです。

1. ブロック分割: 配列を \(\sqrt{N}\) 個のブロックに分割します
2. クエリのソート: クエリを「左端が属するブロック番号」でソートし、同じブロック内では「右端」でソートします
3. しゃくとり法的処理: 現在の区間 \([cur\_l, cur\_r]\) を目的の区間 \([l, r]\) に変形しながら処理します

具体的な処理の流れ

現在の区間: [cur_l, cur_r]（最初は空）
目的の区間: [l, r]

1. cur_r < r なら、cur_r を右に伸ばしながら要素を追加
2. cur_l > l なら、cur_l を左に伸ばしながら要素を追加
3. cur_r > r なら、cur_r を左に縮めながら要素を削除
4. cur_l < l なら、cur_l を右に縮めながら要素を削除

例での説明

配列 \(P = [1, 2, 1, 3, 2]\) で区間 \([1, 3]\) の品種数を求める場合： - 花壇1: 品種1、花壇2: 品種2、花壇3: 品種1 - 登場する品種は {1, 2} なので、答えは 2

計算量

• 時間計算量: \(O((N + Q)\sqrt{N})\)

  • 左端の移動: 同一ブロック内で最大 \(O(\sqrt{N})\)、ブロックをまたぐ移動は \(O(Q)\) 回
  • 右端の移動: 各ブロック内で \(O(N)\)、ブロックは \(O(\sqrt{N})\) 個
  • 合計で \(O(N\sqrt{N} + Q\sqrt{N})\)

• 空間計算量: \(O(N + Q)\)

  • 配列 \(P\): \(O(N)\)
  • クエリの保存: \(O(Q)\)
  • 品種のカウント配列: \(O(N)\)

実装のポイント

1. 0-indexed への変換: 入力は1-indexedなので、内部処理では0-indexedに変換すると扱いやすい

2. 奇偶ブロックの最適化: 偶数番目のブロックでは右端を昇順、奇数番目では降順にソートすることで、右端の移動距離を減らせます

   if block % 2 == 0:
      return (block, r)
   else:
      return (block, -r)
   

3. 区間の拡大・縮小の順序:

   • 拡大を先に行う（cur_r < r, cur_l > l の処理を先に）
   • 縮小を先にすると、空の区間を作ってしまう可能性があります

4. defaultdict の活用: 品種のカウントに defaultdict(int) を使うことで、初期化を気にせず実装できます

5. 答えの復元: クエリをソートして処理するため、元のクエリ番号を保持しておき、最後に正しい順序で出力します

   ソースコード

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    P = list(map(int, input().split()))
    
    queries = []
    for i in range(Q):
        L, R = map(int, input().split())
        queries.append((L - 1, R - 1, i))  # 0-indexed
    
    # Mo's algorithm
    block_size = max(1, int(N ** 0.5))
    
    # Sort queries by (L // block_size, R) with optimization for odd/even blocks
    def mo_cmp(q):
        l, r, idx = q
        block = l // block_size
        if block % 2 == 0:
            return (block, r)
        else:
            return (block, -r)
    
    queries.sort(key=mo_cmp)
    
    # Count array and current distinct count
    count = defaultdict(int)
    distinct = 0
    
    def add(idx):
        nonlocal distinct
        val = P[idx]
        if count[val] == 0:
            distinct += 1
        count[val] += 1
    
    def remove(idx):
        nonlocal distinct
        val = P[idx]
        count[val] -= 1
        if count[val] == 0:
            distinct -= 1
    
    answers = [0] * Q
    cur_l, cur_r = 0, -1
    
    for l, r, idx in queries:
        # Expand/shrink the range [cur_l, cur_r] to [l, r]
        while cur_r < r:
            cur_r += 1
            add(cur_r)
        while cur_l > l:
            cur_l -= 1
            add(cur_l)
        while cur_r > r:
            remove(cur_r)
            cur_r -= 1
        while cur_l < l:
            remove(cur_l)
            cur_l += 1
        
        answers[idx] = distinct
    
    print('\n'.join(map(str, answers)))

if __name__ == "__main__":
    main()

---

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