P17154 [ICPC 2017 Xi'an R] Acedia

给定一个包含 $n$ 个数的序列，第 $k$ 个数为 $a[k]$。 你需要回答 $m$ 个询问。 每个询问的要求是：对于 $k$ 从 $1$ 到 $10$ 的每一个值，计算区间 $[l,r]$ 中满足条件的对 $(x, x+k-1)$ 的数量。 我们称一对 $(x,y)$ 是 **有效的**，当且仅当： 1. 对于从 $x$ 到 $y$ 的每一个 $i$，区间 $[l,r]$ 中至少存在一个元素等于 $i$； 2. 区间 $[l,r]$ 中不存在等于 $x-1$ 或 $y+1$ 的元素。

输入包含多组测试数据。 第一行包含一个整数 $T$ $(1 \le T \le 5)$，表示测试数据的组数。 对于每组测试数据： 第一行包含两个整数 $n, m$ $(1 \le n,m \le 1000000)$。 接下来一行包含 $n$ 个整数，依次表示 $a[1],\dots, a[n]$ $(0 \le a[i] \le 2000000000)$。 随后的 $m$ 行，每行包含两个整数 $l, r$，表示一个针对区间 $[l,r]$ 的询问 $(1 \le l \le r \le n)$。

对于每个询问，你需要输出 $10$ 个数。为减少输出量，只需将每个数对 $10$ 取模后输出，中间不加空格。 对于每组测试数据，输出 $m$ 行。第 $k$ 行包含一个长度为 $10$ 的字符串，表示第 $k$ 个询问的答案。

翻译由 DeepSeek V4 Pro 完成