← 返回题目列表

AtCoder · abc174_f

F. 范围设置查询

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

分数: 600 点

问题陈述

我们有 N 彩球从左到右排列成一排;的颜色 i从左边数第一个球是 c_i.

你被给予 Q 查询。的 i第一个查询如下:有多少种不同的颜色 l_i-th 通过 r_i左边第一个球有?

约束

  • 1\leq N,Q \leq 5 \times 10^5
  • 1\leq c_i \leq N
  • 1\leq l_i \leq r_i \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

输出

打印 Q 行。的 i- 第行应包含对 i-第一个查询。


示例输入 1

4 3
1 2 1 3
1 3
2 4
3 3

示例输出 1

2
3
1
  • 的 1-st, 2-nd,和 3- 从左边起第一个球有以下颜色 1, 2,和 1 - 两种不同的颜色。
  • 的 2-st, 3-rd,和 4从左边起第一个球有以下颜色 2, 1,和 3 - 三种不同的颜色。
  • 的 3- 从左边起第一个球有颜色 1 - 只有一种颜色。

示例输入 2

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

示例输出 2

1
2
2
1
2
2
6
3
3
3