AtCoder Beginner Contest 174
翻译中…
Problem Statement
翻译中…
We have $N$ colored balls arranged in a row from left to right; the color of the $i$-th ball from the left is $c_i$.
翻译中…
You are given $Q$ queries. The $i$-th query is as follows: how many different colors do the $l_i$-th through $r_i$-th balls from the left have?
翻译中…
Constraints
翻译中…
$1\leq N,Q \leq 5 \times 10^5$$1\leq c_i \leq N$$1\leq l_i \leq r_i \leq N$- All values in input are integers.
翻译中…
Input
翻译中…
Input is given from Standard Input in the following format:
翻译中…
N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q翻译中…
Output
翻译中…
Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query.
翻译中…
样例
Input #1
4 3
1 2 1 3
1 3
2 4
3 3
Output #1
2
3
1
- The $1$-st, $2$-nd, and $3$-rd balls from the left have the colors $1$, $2$, and $1$ - two different colors.
- The $2$-st, $3$-rd, and $4$-th balls from the left have the colors $2$, $1$, and $3$ - three different colors.
- The $3$-rd ball from the left has the color $1$ - just one color.
Input #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
Output #2
1
2
2
1
2
2
6
3
3
3
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。