P14479 Generating Sequence

**Hint: Please note the constraints on $n$ and $q$ in this problem.** Let $\text{len}(a)$ denote the length of sequence $a$, and $a_{[l,r]}$ denote the subsequence of $a$ from index $l$ to $r$ inclusive. Initially, Little L has an empty sequence $b$. Little L can perform the following operations in order several times to eventually transform $b$ into the target sequence $a$: - Generate a sequence $c$ such that $\text{len}(b)\leq\text{len}(c)$. - If there exists $1\leq i\leq\text{len}(b)$ such that $b_i=c_i$, then gain $1$ point; otherwise, gain $0$ points. - Append sequence $c$ to the end of sequence $b$. Little L wants to know, under the goal of achieving the target sequence, what is the maximum number of points that can be obtained. Let $f(a)$ be the answer to this problem when $a$ is the target sequence. To prevent you from cheating Little L, Little L will first give you an array $a$ and then perform $q$ queries. Each query gives two integers $l, r$, and you need to answer the value of $f(a_{[l,r]})$.

The first line contains two integers $n, q$, representing the length of sequence $a$ and the number of queries, respectively. The second line contains $n$ non-negative integers $a_i$. Then, $q$ lines follow, each with two integers $l, r$, representing the query interval.

Output $q$ lines, each containing an integer, representing the value of $f(a_{[l,r]})$ for each query.

**【Sample Explanation】** For the first query, the sequence is $a_{[1,9]}=\{3,3,3,1,0,2,0,1,0\}$. One possible way to achieve the maximum points is as follows: - First operation: let $c=\{3\}$, gain $0$ points, now $b=\{3\}$. - Second operation: let $c=\{3\}$, gain $1$ point, now $b=\{3,3\}$. - Third operation: let $c=\{3,1\}$, gain $1$ point, now $b=\{3,3,3,1\}$. - Fourth operation: let $c=\{0,2,0,1,0\}$, gain $1$ point, now $b=\{3,3,3,1,0,2,0,1,0\}$. The total points gained is $3$. It can be proven that no scheme can gain more than $3$ points. **【Data Range】** **This problem uses bundled tests.** | Subtask | $n$ | $q$ | Special Constraints | Score | | :------: | :------: | :------: | :------------------: | :---: | | $1$ | $\leq20$ | $\leq10$ | None | $8$ | | $2$ | $\leq300$ | $\leq10$ | None | $9$ | | $3$ | $\leq5\times10^3$ | $\leq10$ | None | $12$ | | $4$ | $\leq10^5$ | $\leq10$ | A | $10$ | | $5$ | $\leq10^5$ | $\leq10$ | B | $13$ | | $6$ | $\leq10^5$ | $\leq10$ | None | $11$ | | $7$ | $\leq10^6$ | $\leq10$ | None | $11$ | | $8$ | $\leq10^6$ | $\leq50$ | None | $26$ | - Special Constraint A: $a_i\leq50$. - Special Constraint B: Each number in sequence $a$ appears at most $50$ times. For all data, $1\leq n\leq10^6$, $1\leq q\leq50$, $1\leq l\leq r\leq n$, $1\leq a_i\leq n$.