P17154 [ICPC 2017 Xi'an R] Acedia

You are given a sequence of $n$ numbers, the $k$-th number is $a[k]$. You need to answer $m$ queries. Each query is: for each $k$ from $1$ to $10$, calculate the number of valid pairs $(x, x+k-1)$ in range $[l,r]$. We call a pair $(x,y)$ valid when: 1. For each $i$ from $x$ to $y$, there exists at least one element in range $[l,r]$ which is equal to $i$. 2. There is no element in range $[l,r]$ which is equal to $x-1$ or $y+1$.

The input contains multiple test cases. The first line contains a number $T$ $(1 \le T \le 5)$ denoting the number of test cases. In each test case: The first line contains two numbers $n, m$. $(1 \le n,m \le 1000000)$. Then one line contains $n$ numbers indicating $a[1]\dots a[n]$. $(0 \le a[i] \le 2000000000)$ The following $m$ lines each contain two numbers $l, r$ denoting a query in range $[l,r]$. $(1 \le l \le r \le n)$

For each query you need to output $10$ numbers. In order to reduce the amount of output, you just need to output each number mod $10$, without space. For each test case, output $m$ lines. The $k$-th line contains a string of length $10$ indicating the answers of the $k$-th query.