【ybt金牌导航6-4-5】【luogu P2709】小明的询问 / 小B的询问（莫队）

题目描述

给定一个长度为 $n$ 的序列 $a$，有 $m$ 次询问，每次询问给定两个整数 $l$ 和 $r$，求 $a_l,a_{l+1},\cdots,a_r$ 中不同数字的个数。

输入格式

第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数，表示序列 $a$。

接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示一次询问。

输出格式

对于每个询问，输出一个整数，表示 $a_l,a_{l+1},\cdots,a_r$ 中不同数字的个数。

数据范围

$1\leq n,m\leq 10^5$，$1\leq a_i\leq 10^6$

输入样例

5 3

1 2 1 3 4

1 3

2 4

1 5

输出样例

2

2

4

算法1

(莫队) $O(n\sqrt{n})$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码