F - 范围集合查询

得分：600分

问题描述

我们有N个彩色的球从左到右排列着，第i个球的颜色是$c_i$。

你会得到Q个查询。第i个查询如下：从左至右，第$l_i$个到第$r_i$个彩球有多少种不同的颜色？

约束条件

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

输入

输入的格式如下：

$N$ $Q$

$c_1$ $c_2$ $\cdots$ $c_N$

$l_1$ $r_1$

$l_2$ $r_2$

$:$

$l_Q$ $r_Q$

输出

输出Q行。第i行应包含第i个查询的结果。

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

2
3
1

• 从左到右的第1, 2, 3个彩球的颜色为1, 2, 1，共两种不同的颜色。
• 从左到右的第2, 3, 4个彩球的颜色为2, 1, 3，共三种不同的颜色。
• 从左到右的第3个彩球的颜色为1，只有一种颜色。

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

1
2
2
1
2
2
6
3
3
3