AGC #005-D ~K Perm Counting

日本語につき問題文は略。

agc005.contest.atcoder.jp

与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。

• クエリ : 区間 中に出現する数の種類数を求めよ

以下の制約で、効率的に解くことはできるだろうか？

• 数列の長さ：
• 要素の値：
• クエリの数：

以下、解法を3つ紹介する。