分数: 600 点
问题陈述
我们有 N 彩球从左到右排列成一排;的颜色 i从左边数第一个球是 c_i.
你被给予 Q 查询。的 i第一个查询如下:有多少种不同的颜色 l_i-th 通过 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-第一个查询。
示例输入 1
4 3 1 2 1 3 1 3 2 4 3 3
示例输出 1
2 3 1
- 的 1-st, 2-nd,和 3- 从左边起第一个球有以下颜色 1, 2,和 1 - 两种不同的颜色。
- 的 2-st, 3-rd,和 4从左边起第一个球有以下颜色 2, 1,和 3 - 三种不同的颜色。
- 的 3- 从左边起第一个球有颜色 1 - 只有一种颜色。
示例输入 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