【ybt金牌导航6-4-1】区间不同数 / 莫队例题

题目描述

给定一个长度为 $n$ 的序列 $a$，有 $m$ 个询问，每个询问给定两个整数 $l,r$，求区间 $[l,r]$ 中不同数的个数。

输入格式

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

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

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

输出格式

对于每个询问，输出区间 $[l,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++ 代码