← 返回题目列表

AtCoder · awc0015_e

E. 数一下花的种类

中文机器翻译题面 查看原题

分数: 466 分

问题陈述

高桥在一家植物园担任管理员。花园里有 N 花坛排列成直线,编号 1, 2, \ldots, N 从左到右。每个花坛 i (1 \leq i \leq N) 包含品种编号的花 P_i。物种编号是介于 1 和 N 包括在内,并且不同的花坛可能包含相同种数的花朵。

植物园有 Q 旅游参观预定。的 i第3次巡演 (1 \leq i \leq Q) 从花坛参观范围 L_i 到花坛 R_i (含)。

高桥想提前知道每次旅行的参观范围内有多少种不同类型的花卉,以便为每次旅行准备导游。

对于每次游览,确定从花坛开始的范围内包含的不同物种编号的数量 L_i 到花坛 R_i.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq P_i \leq N (1 \leq i \leq N)
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
  • 所有输入均为整数

输入

N Q
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含一个整数 N 代表花坛数量和一个整数 Q 代表游览次数,以空格分隔。
  • 第二行包含整数 P_1, P_2, \ldots, P_N 代表每个花坛种植的花卉的种类编号,以空格分隔。
  • 以下 Q 行给出了每个旅行团的参观范围。
  • 的 i- 第这些行 (1 \leq i \leq Q) 包含左端点 L_i 和右端点 R_i 的访问范围 i第 次游览,以空格分隔。

输出

输出 Q 行。的 i第行 (1 \leq i \leq Q) 应包含从花坛开始的范围内的不同物种编号的数量 L_i 到花坛 R_i 为 i第 次巡演。


示例输入 1

5 3
1 2 1 3 2
1 3
2 5
1 5

示例输出 1

2
3
3

示例输入 2

10 5
3 1 4 1 5 9 2 6 5 3
1 5
3 7
1 10
5 5
2 8

示例输出 2

4
5
7
1
6

示例输入 3

20 8
5 3 5 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 4
1 20
1 1
10 15
5 10
1 10
11 20
7 14
3 8

示例输出 3

5
1
5
5
5
5
5
5