#P5070. [Ynoi2015] 即便看不到未来

[Ynoi2015] 即便看不到未来

题目背景


我不会再闷闷不乐了
那撕裂胸口的悲伤
还有快流下来的眼泪
全都是塑造出现在的我的东西

烦恼
灰心
痛苦
喜悦
全部不可或缺
现在站在这里的不是别人

毫无疑问是我自己,是珂朵莉
对,至少现在如此

记忆慢慢地缺失
人格在逐渐崩坏
抱歉
你们当中
已经有一半的人我不记得了...
忘记的名字还可以重新记住
但是失去的记忆却无可挽回
这个将要崩坏的自己,还能被称作珂朵莉吗...?

可即便这样的感情,我也想要毫无保留地去珍惜
因为如果连这种感情都失去的时候
我大概就会...彻底消失吧

题目描述

珂朵莉给了你一个序列,每次查询一段区间中长度为 1,2,,101,2,\ldots,10 的极长值域连续段个数。 定义值域连续段为:

  • 把区间里面所有数排序后去重,设排序后得到的序列为 bb
  • 如果对于二元组 (l,r)(l,r) 满足 bl,bl+1,,brb_l,b_{l+1},\ldots,b_r 中每个数为前一个数 +1+1
  • 而且对于二元组 (l,r+1)(l,r+1)(l1,r)(l-1,r) 均不满足,我们称 (l,r)(l,r) 为一个长度为 rl+1r-l+1 的极长值域连续段。

输入格式

第一行两个整数 n,mn,m,表示序列的长度和查询的次数。

之后一行 nn 个整数表示这个序列。

之后 mm 行每行两个整数 l,rl,r 表示查询的区间。

输出格式

对于每次询问,输出一个长度为 1010 的字符串,第 ii 个字符表示长度为 ii 的极长连续段个数 mod10\bmod 10的结果。

8 9
2 3 3 3 3 6 6 6
1 8
2 3
4 5
6 8
1 2
3 4
5 6
3 8
5 5
1100000000
1000000000
1000000000
1000000000
0100000000
1000000000
2000000000
2000000000
1000000000

提示

Idea:nzhtl1477,Solution:nzhtl1477,Code:mcfx,Data:nzhtl1477

对于 100%100\% 的数据,1n,m,ai1061\leq n,m,a_i\leq10^61lrn1\leq l\leq r\leq n