概要

\(N\) 個の要素を持つ配列に対し、指定された範囲 \([L, R]\) 内に何種類の異なる値が含まれているかを答えるクエリに \(Q\) 回回答する問題です。この問題は「Range Distinct Elements Query」と呼ばれる典型的な問題であり、クエリを先読みして処理する「オフラインクエリ」の手法を用いることで効率的に解くことができます。

考察

素朴なアプローチ

各クエリに対して、範囲 \([L, R]\) の要素を走査し、set（集合）などのデータ構造を使って種類数を数える方法が考えられます。しかし、この方法では 1 クエリあたり最大で \(O(N)\) の時間がかかり、全体で \(O(NQ)\) となります。制約が \(N, Q \leq 10^5\) であるため、最悪ケースで \(10^{10}\) 回程度の計算が必要になり、実行時間制限（TLE）に間に合いません。

効率的なアプローチのヒント

この問題の肝は、「ある値が範囲内に複数ある場合、一番右側（インデックスが大きい方）にあるものだけをカウントすればよい」という点にあります。

例えば、配列が [1, 2, 1, 3] で範囲が \([1, 3]\)（1-indexed）の場合、値 1 はインデックス 1 と 3 に現れます。右端 \(R=3\) までに注目したとき、インデックス 1 の 1 は無視して、インデックス 3 の 1 だけを「種類数のカウント対象」としてマークしても、結果は変わりません。

このように「右端を固定して考える」ために、クエリを右端 \(R\) の昇順にソートして処理するオフラインクエリの手法が有効です。

アルゴリズム

1. クエリのソート: 全てのクエリ \((L_i, R_i)\) を、右端 \(R_i\) の昇順に並べ替えます。
2. データ構造の準備: 1 点更新と区間和取得が高速に行える Binary Indexed Tree (BIT / Fenwick Tree) を用意します。
3. 配列の走査:
   • インデックス \(r\) を \(1\) から \(N\) まで進めながら、以下の操作を行います。
   • 現在見ている値 \(P_r\) が、以前にインデックス \(prev\) で出現していた場合、BIT の \(prev\) 番目の値を -1 します（古い位置のカウントを消す）。
   • BIT の現在の位置 \(r\) を +1 します（最新の位置をカウント対象にする）。
   • 値 \(P_r\) の最新の出現位置を \(r\) に更新します。
   • もし、現在の \(r\) があるクエリの右端 \(R_i\) と一致していれば、そのクエリの答えを求めます。答えは BIT における区間 \([L_i, R_i]\) の和（つまり query(R_i) - query(L_i - 1)）となります。

この方法では、BIT に「各数値の最新の出現位置」にだけ 1 が立っている状態を作ることができます。そのため、区間 \([L, R]\) の和を取ることで、その範囲内に「最新の出現位置」を持つ数値の種類数を正しく数えることができます。

計算量

• 時間計算量: \(O((N + Q) \log N + Q \log Q)\)
  • クエリのソートに \(O(Q \log Q)\) かかります。
  • 配列の走査 \(N\) 回と、クエリへの回答 \(Q\) 回のそれぞれで BIT の操作（\(O(\log N)\)）を行うため、全体で \(O((N + Q) \log N)\) となります。
• 空間計算量: \(O(N + Q)\)
  • 配列 \(P\)、BIT、クエリの保存、および各数値の最終出現位置を記録する配列（またはハッシュマップ）に \(O(N + Q)\) のメモリを使用します。

実装のポイント

• オフライン処理: クエリをソートして処理するため、元の順番を保持しておく必要があります（コード内では (r, l, i) のように元のインデックス i を保持しています）。

• 高速な入出力: \(N, Q\) が大きいため、Python では sys.stdin.read().split() や sys.stdout.write を使用して入出力を高速化するのが一般的です。

• BIT のインデックス: BIT は通常 1-indexed で実装するため、配列の 0-indexed との変換に注意が必要です。

  ソースコード

import sys

def solve():
    # 入力の高速化
    input = sys.stdin.read().split()
    if not input:
        return
    
    N = int(input[0])
    Q = int(input[1])
    P = list(map(int, input[2:N+2]))
    
    queries = []
    idx = N + 2
    for i in range(Q):
        l = int(input[idx])
        r = int(input[idx+1])
        queries.append((r, l, i))
        idx += 2
    
    # クエリを右端 R の昇順にソート
    queries.sort()
    
    # Binary Indexed Tree (Fenwick Tree) の実装
    bit = [0] * (N + 1)
    
    def update(i, delta):
        while i <= N:
            bit[i] += delta
            i += i & (-i)
            
    def query(i):
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & (-i)
        return s

    ans = [0] * Q
    last_pos = {}
    current_r = 0
    
    for r, l, original_idx in queries:
        # 現在の右端 r まで BIT を更新
        while current_r < r:
            current_r += 1
            val = P[current_r - 1]
            if val in last_pos:
                # 以前に出現した位置のフラグを消す
                update(last_pos[val], -1)
            # 新しい出現位置にフラグを立てる
            update(current_r, 1)
            last_pos[val] = current_r
            
        # [L, R] の範囲にある種類の数は、BITの区間和 [L, R]
        ans[original_idx] = query(r) - query(l - 1)
        
    # 結果を出力
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。