区间不同元素个数(D-query)

题目描述

给定一个包含 $n$ 个数字的序列 $a_1, a_2, \cdots, a_n$ 和若干 d-query。每个 d-query 是一对 $(i, j)$（$1 \le i \le j \le n$）。对于每个 d-query $(i, j)$，你需要返回子序列 $a_i, a_{i+1}, \cdots, a_j$ 中不同元素的数量。

输入格式

• 第 $1$ 行：一个整数 $n$（$1 \le n \le 30000$）。
• 第 $2$ 行：$n$ 个数字 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^6$）。
• 第 $3$ 行：一个整数 $q$（$1 \le q \le 200000$），表示 d-query 的数量。
• 接下来 $q$ 行，每行包含两个整数 $i, j$，表示一个 d-query（$1 \le i \le j \le n$）。

输出格式

• 对于每个 d-query $(i, j)$，在一行中输出子序列 $a_i, a_{i+1}, \cdots, a_j$ 中不同元素的数量。

样例输入 #1

5
1 1 2 1 3
3
1 5
2 4
3 5

样例输出 #1

3
2
3

数据范围

由 deepseek 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接