分数: 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