AT_abc174_f [ABC174F] Range Set Query

题目描述

有 $N$ 个带有颜色的珠子从左到右排成一列，从左起第 $i$ 个珠子的颜色为 $c_i$。

现在有 $Q$ 个查询。对于第 $i$ 个查询，请回答从左起第 $l_i$ 个到第 $r_i$ 个珠子之间，有多少种不同的颜色。

输入格式

输入以以下格式从标准输入给出。

$N$ $Q$ $c_1$ $c_2$ $\cdots$ $c_N$ $l_1$ $r_1$ $l_2$ $r_2$ $\cdots$ $l_Q$ $r_Q$

输出格式

请输出 $Q$ 行。第 $i$ 行输出第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
3
1

输入输出样例 #2

输入 #2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

输出 #2

1
2
2
1
2
2
6
3
3
3

说明/提示

限制条件

• $1 \leq N, Q \leq 5 \times 10^5$
• $1 \leq c_i \leq N$
• $1 \leq l_i \leq r_i \leq N$
• 所有输入均为整数。

样例解释 1

• 第 $1,2,3$ 个珠子的颜色分别为 $1,2,1$，其中有 $2$ 种颜色：$1,2$。
• 第 $2,3,4$ 个珠子的颜色分别为 $2,1,3$，其中有 $3$ 种颜色：$1,2,3$。
• 第 $3$ 个珠子的颜色为 $1$，其中有 $1$ 种颜色：$1$。

由 ChatGPT 4.1 翻译