P5070 [Ynoi Easy Round 2015] Even If I Cannot See the Future

 I will not be depressed anymore. That sadness that tears open my chest, and the tears that are about to fall, are all things that shaped who I am now.  Worries, discouragement, pain, joy, none of them can be missing. The one standing here now is not someone else.  Without a doubt, it is me myself, it is Ke Duoli (pinyin: Kē Duō Lí). Yes, at least for now.  My memories are slowly disappearing, and my personality is gradually falling apart. Sorry. Among you, there are already half of you that I cannot remember... Forgotten names can be remembered again, but lost memories can never be recovered. Can this self that is about to collapse still be called Ke Duoli...?  But even with feelings like this, I still want to cherish them without holding anything back. Because if I lose even this kind of feeling, I will probably... disappear completely.

Ke Duoli gives you a sequence. For each query, you need to count, in a given interval, the number of maximal consecutive value-range segments of lengths $1,2,\ldots,10$. A consecutive value-range segment is defined as follows: * Sort all numbers in the interval and remove duplicates. Let the resulting sequence be $b$. * For a pair $(l,r)$, if every number in $b_l,b_{l+1},\ldots,b_r$ is equal to the previous number $+1$. * And for the pairs $(l,r+1)$ and $(l-1,r)$, neither satisfies the condition above, then we call $(l,r)$ a maximal consecutive value-range segment, with length $r-l+1$.

The first line contains two integers $n,m$, representing the length of the sequence and the number of queries. The next line contains $n$ integers representing the sequence. Then follow $m$ lines, each containing two integers $l,r$, representing the query interval.

For each query, output a string of length $10$. The $i$-th character represents the number of maximal consecutive segments of length $i$ modulo $10$.

Idea: nzhtl1477, Solution: nzhtl1477, Code: mcfx, Data: nzhtl1477. For $100\%$ of the testdata, $1\leq n,m,a_i\leq10^6$, $1\leq l\leq r\leq n$. Translated by ChatGPT 5