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$ : $l_Q$ $r_Q$

输出格式

输出 $Q$ 行。第 $i$ 行应当包含第 $i$ 个查询的答案。

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

2
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

提示

$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$、第 $2$、第 $3$ 个球的颜色分别是 $1$、$2$、$1$——两种不同的颜色。 从左数第 $2$、第 $3$、第 $4$ 个球的颜色分别是 $2$、$1$、$3$——三种不同的颜色。 从左数第 $3$ 个球的颜色是 $1$——只有一种颜色。

标签: AtCoder|abc174F

来源

AtCoder|abc174F