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

lhb25 阅读:78 2023-05-01 21:59:20 评论:0

题目描述

给定一个长度为 $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++ 代码


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

关注我们

一个IT知识分享的公众号