#O1058. 区间不同数
区间不同数
题目描述
给定长度为 的序列 ,回答 次询问:每次给出 ,求 中不同数的个数。
题目类型
莫队算法
输入格式
第一行两个整数 。
第二行 个整数。
接下来 行,每行两个整数 。
输出格式
共 行,每行一个整数表示答案。
样例 #1
样例输入 #1
5 2
1 2 1 3 2
1 3
2 5
样例输出 #1
2
3
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 长度与询问数 | |
| 数值范围 |
- 按块排序后移动指针,维护计数数组与当前不同数个数。
给定长度为 n 的序列 a,回答 q 次询问:每次给出 l,r,求 al∼ar 中不同数的个数。
莫队算法
第一行两个整数 n,q。
第二行 n 个整数。
接下来 q 行,每行两个整数 l,r。
共 q 行,每行一个整数表示答案。
5 2
1 2 1 3 2
1 3
2 5
2
3
| 数据范围 | 说明 |
|---|---|
| 1≤n,q≤105 | 长度与询问数 |
| 1≤ai≤n | 数值范围 |