#O1058. 区间不同数

区间不同数

题目描述

给定长度为 nn 的序列 aa,回答 qq 次询问:每次给出 l,rl, r,求 al∼ara_l \sim a_r 中不同数的个数。

题目类型

莫队算法

输入格式

第一行两个整数 n,qn, q。

第二行 nn 个整数。

接下来 qq 行,每行两个整数 l,rl, r。

输出格式

共 qq 行,每行一个整数表示答案。

样例 #1

样例输入 #1

5 2
1 2 1 3 2
1 3
2 5

样例输出 #1

2
3

数据规模与约定

数据范围 说明
1≤n,q≤1051 \le n, q \le 10^5 长度与询问数
1≤ai≤n1 \le a_i \le n 数值范围
  • 按块排序后移动指针,维护计数数组与当前不同数个数。