概要

各クエリ区間 \([L,R]\) に含まれる「異なる値（品種番号）」の個数を、\(N,Q \le 10^5\) の制約下で高速に求める問題です。

考察

重要な気づき

区間内の「種類数」は、その区間内で 各品種が最後に現れる位置 だけを数えれば求まります。

たとえば \(P = [1,2,1,3,2]\) のとき、\(R=5\) まで見たとすると
- 品種1の最後の出現: 位置3
- 品種2の最後の出現: 位置5
- 品種3の最後の出現: 位置4

このとき区間 \([L,5]\) に含まれる種類数は、「最後の出現位置が \(L\) 以上にある品種の数」と一致します。

素朴解がダメな理由

各クエリごとに \([L,R]\) を走査して集合で数えると \(O((R-L+1))\) かかり、最悪で \(Q\) 回あるので \(O(NQ)\) となり、\(10^{10}\) 規模でTLEになります。

どう解決するか

右端 \(R\) を小さい順にクエリを並べ、左から順に配列を見ながら「最後の出現位置」情報を更新していきます。
このとき「最後の出現位置たち」を 1 次元上の点として管理し、区間和で数えられるようにすると高速です。

アルゴリズム

Fenwick木（BIT） を使って、次を実現します。

• BITの各位置 \(i\) に値 \(1/0\) を持たせる
  
  • 「位置 \(i\) が、ある品種の 現在の最後の出現位置 なら 1」
  • そうでなければ 0
    
• したがって、ある時点（ある \(R\) まで処理済み）での \([L,R]\) の種類数は BIT の区間和 \(\sum_{i=L}^{R} \text{BIT}[i]\) で求まります。

処理手順は以下です。

1. クエリ \((L_i,R_i)\) を「\(R_i\) 昇順」にソートして保持する（元の順番に戻すため index も持つ）。
2. \(i=1\) から \(N\) まで順に見ていく（現在位置を \(i\) とする）。
3. 値 \(v=P_i\) について、直前の出現位置 prev = last[v] を見る。
   • prev > 0 なら、そこは「最後の出現」ではなくなるので BITで add(prev, -1)。
   • 新しい最後の出現位置として BITで add(i, +1)。
   • last[v] = i に更新。
4. 「右端がちょうど \(R=i\) のクエリ」をすべて処理し、答えを
   \(\text{BIT.range\_sum}(L, R)\) で求める。

小さな例

\(P=[1,2,1,3,2]\) を左から処理すると、\(i=5\) 時点では BIT には
最後の出現位置（3,4,5）にだけ 1 が立っています。
よってクエリ \([2,5]\) の答えは BIT の \(2..5\) の和で \(3\)（品種1,2,3）になります。

計算量

• 時間計算量: \(O\big((N+Q)\log N\big)\)
  （各要素更新が \(\log N\)、各クエリ回答が \(\log N\)）
• 空間計算量: \(O(N+Q)\)
  （BIT配列、last配列、クエリ配列、答え配列）

実装のポイント

• クエリを \(R\) でソートし、配列を左から走査しながら「今処理できるクエリ」をまとめて答えます（オフライン処理）。

• last[v] は「品種 \(v\) が最後に出現した位置」。同じ品種が再登場したら、前の位置を -1 して新しい位置を +1 します。

• BITは 1-indexed で実装すると典型的でバグりにくいです（コードでも P=[0]+... として調整）。

• 入力が大きいので sys.stdin.buffer.read() でまとめ読みすると高速です。

  ソースコード

import sys

class Fenwick:
    __slots__ = ("n", "bit")
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, x):
        n = self.n
        bit = self.bit
        while i <= n:
            bit[i] += x
            i += i & -i

    def sum(self, i):
        s = 0
        bit = self.bit
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.sum(r) - self.sum(l - 1)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)
    P = [0] + [next(it) for _ in range(N)]

    queries = []
    for idx in range(Q):
        l = next(it); r = next(it)
        queries.append((r, l, idx))
    queries.sort()

    fw = Fenwick(N)
    last = [0] * (N + 1)
    ans = [0] * Q

    qi = 0
    for i in range(1, N + 1):
        v = P[i]
        prev = last[v]
        if prev:
            fw.add(prev, -1)
        fw.add(i, 1)
        last[v] = i

        while qi < Q and queries[qi][0] == i:
            r, l, idx = queries[qi]
            ans[idx] = fw.range_sum(l, r)
            qi += 1

    sys.stdout.write("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。