| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 93 | 3 | 3 | 30.000% |
You are given a sequence $a_1,\dots , a_n$ and $q$ independent queries. In each query you are given two integers $l$ and $r$. Consider the sequence $a_l , a_{l+1}, \dots , a_r$. Your task is to compute the sum of the minimum excluded element of all sequences of form $a_i , a_{i+1}, \dots , a_j$, for $l ≤ i ≤ j ≤ r$.
The minimum excluded element of a sequence is the smallest non-negative integer that does not appear in the sequence. For example, for the sequence $0$, $1$, $4$, $2$ it is $3$, but the for the sequence $1$, $2$, $3$, $4$ it is $0$.
The first line of the input contains the integers $n$ and $q$. The second line contains $n$ integers $a_1, a_2, \dots , a_n$, representing the initial sequence. Each of the next $q$ lines contains two integers $l$ and $r$, describing each query.
The output should contain the answers to the $q$ queries in order, each on a new line.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $1 ≤ a_i ≤ n$ |
| 2 | 10 | $1 ≤ q ≤ 200$; $r - l ≤ 200$ |
| 3 | 12 | $1 ≤ n ≤ 5000$ |
| 4 | 15 | Each number from $0$ to $n - 1$ appears exactly once in $a_1, a_2, \dots , a_n$. |
| 5 | 15 | $0 ≤ a_i ≤ 100$ and there are no two queries $i$ and $j$ such that $l_i < l_j$ and $r_j < r_i$. |
| 6 | 22 | $l = 1$ for each query. |
| 7 | 23 | No further restrictions. |
6 3 0 1 2 0 1 3 1 2 3 5 1 6
3 7 39
Explanation for the first queries:
| Subsequence | Min. excl. elem. |
|---|---|
| $0$ | $1$ |
| $1$ | $0$ |
| $0$, $1$ | $2$ |
| Total: | $3$ |
Explanation for the second queries:
| Subsequence | Min. excl. elem. |
|---|---|
| $2$ | $0$ |
| $0$ | $1$ |
| $1$ | $0$ |
| $2$, $0$ | $1$ |
| $0$, $1$ | $2$ |
| $2$, $0$, $1$ | $3$ |
| Total: | $7$ |
Explanation for the third query:
| Subsequence | Min. excl. elem. |
|---|---|
| $0$ | $1$ |
| $0$, $1$ | $2$ |
| $0$, $1$, $2$ | $3$ |
| $0$, $1$, $2$, $0$ | $3$ |
| $0$, $1$, $2$, $0$, $1$ | $3$ |
| $0$, $1$, $2$, $0$, $1$, $3$ | $4$ |
| $1$ | $0$ |
| $1$, $2$ | $0$ |
| $1$, $2$, $0$ | $3$ |
| $1$, $2$, $0$, $1$ | $3$ |
| $1$, $2$, $0$, $1$, $3$ | $4$ |
| $2$ | $0$ |
| $2$, $0$ | $1$ |
| $2$, $0$, $1$ | $3$ |
| $2$, $0$, $1$, $3$ | $4$ |
| $0$ | $1$ |
| $0$, $1$ | $2$ |
| $0$, $1$, $3$ | $2$ |
| $1$ | $0$ |
| $1$, $3$ | $0$ |
| $3$ | $0$ |
| Total: | $39$ |
Contest > infO(1) Cup > infO(1) Cup 2022 A번