概要

与えられた区間内の花の品種の種類数を、複数のクエリに対して高速に求める問題です。

考察

この問題では、花壇の列が固定されており、それぞれの花壇には品種番号 \(P_i\) が割り当てられています。各クエリごとに、指定された区間 \([L, R]\) 内で出現する異なる品種の数を答える必要があります。

素朴な方法としては、各クエリに対して区間内の要素を走査し、出現する品種を set などで管理することで種類数を数えることが考えられます。しかし、この方法の時間計算量は各クエリに対して最悪 \(O(N)\) かかり、全体では \(O(QN)\) となり、制約 \(N, Q \leq 10^5\) のもとでは最大で \(10^{10}\) 回の計算が必要になり、TLE します。

そこで、Mo’s Algorithm（モのアルゴリズム） を用いることで、複数の区間クエリに対する処理を効率化できます。このアルゴリズムは、クエリを特定の順序でソートし、現在の区間を少しずつ動かしながら答えを更新していくことで、全体の計算量を削減します。

アルゴリズム

Mo’s Algorithm の基本的なアイデアは、「現在の区間の答え」を再利用可能な形で管理しながら、クエリを効率よく処理することです。

アルゴリズムの流れ：

1. クエリをブロックサイズ \(B = \sqrt{N}\) に基づいて以下のようにソートします：
   • 左端 \(L\) を \(B\) で割った商（ブロック番号）でグループ分け
   • 同じブロック内では右端 \(R\) の昇順にソート
2. 最初の区間（例えば最初は空集合）から始めて、クエリの順に区間を「伸び縮み」させながら答えを更新
3. 区間の伸縮に伴って、品種のカウントを管理する配列（辞書など）を使い、出現回数を追跡
4. 品種の種類数は、カウントが 1 以上であるキーの数として管理

具体例：

例えば、花の品種列が [1, 2, 1, 3] で、クエリが [1, 3] だったとします（1-indexed）。これは区間 [1, 2, 1] を意味し、異なる品種は {1, 2} の2種類です。

計算量

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

これは、各要素の追加・削除が \(O(1)\) であり、クエリのソートと移動にかかる時間を考慮したものです。

実装のポイント

• 区間を 0-indexed に変換していることに注意（入力は1-indexed）
• add() と remove() 関数で、カウントおよび種類数の管理を正確に行う
• クエリをソートする際に (L // BLOCK_SIZE, R) をキーとする
• 答えを記録する配列 answers を使い、後でクエリの順序で出力する

## ソースコード

```python
import sys
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    P = list(map(int, data[2:2+N]))
    
    queries = []
    for i in range(Q):
        L = int(data[2 + N + 2*i]) - 1  # 0-indexed
        R = int(data[2 + N + 2*i + 1]) - 1
        queries.append((L, R, i))
    
    # Mo's algorithm
    BLOCK_SIZE = int(N**0.5) + 1
    queries.sort(key=lambda x: (x[0] // BLOCK_SIZE, x[1]))
    
    # Initialize
    count = defaultdict(int)
    distinct = 0
    answers = [0] * Q
    
    current_l = 0
    current_r = -1
    
    def add(idx):
        nonlocal distinct
        count[P[idx]] += 1
        if count[P[idx]] == 1:
            distinct += 1
            
    def remove(idx):
        nonlocal distinct
        count[P[idx]] -= 1
        if count[P[idx]] == 0:
            distinct -= 1
            
    for L, R, idx in queries:
        # Expand to the right
        while current_r < R:
            current_r += 1
            add(current_r)
        # Shrink from the right
        while current_r > R:
            remove(current_r)
            current_r -= 1
        # Expand to the left
        while current_l > L:
            current_l -= 1
            add(current_l)
        # Shrink from the left
        while current_l < L:
            remove(current_l)
            current_l += 1
            
        answers[idx] = distinct
        
    print('\n'.join(map(str, answers)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。