个位数边界

题目描述

小明有一个包含 (n) 个非负整数的序列。

他首先按照每个整数的个位数字从小到大对序列进行排序。

例如，整数 (23)、(45)、(12) 的个位数字分别为 (3)、(5)、(2)，因此按照个位数字排序后，(12) 应排在 (23) 和 (45) 的前面。

如果两个整数的个位数字相同，则它们在排序后的先后顺序不作要求。

排序完成后，小明需要进行 (q) 次查询。

每次给定一个非负整数 (x)，设：

• (L) 为排序后序列中，第一个个位数字大于等于 (x) 的个位数字的位置；
• (R) 为排序后序列中，第一个个位数字严格大于 (x) 的个位数字的位置。

序列的位置从 (0) 开始编号。

如果不存在满足条件的位置，则该位置取 (n)。

对于每次查询，请输出 (L)、(R) 以及 (R-L)。

---

输入格式

第一行包含两个整数 (n,q)，分别表示序列长度和查询次数。

第二行包含 (n) 个非负整数：

a1 a2 ... an

接下来 (q) 行，每行包含一个非负整数 (x)，表示一次查询。

---

输出格式

对于每次查询，输出一行三个整数：

L R R-L

其中：

• (L) 表示第一个个位数字大于等于 (x) 的个位数字的位置；
• (R) 表示第一个个位数字大于 (x) 的个位数字的位置；
• (R-L) 表示序列中个位数字与 (x) 的个位数字相同的元素个数。

---

数据范围

对于所有测试数据：

$1\le n,q\le 10^5$

$0\le a_i,x\le 10^9$

---

样例输入 1

7 5
23 45 12 78 34 67 89
22
35
19
40
101

样例输出 1

0 1 1
3 4 1
6 7 1
0 0 0
0 0 0

---

样例解释 1

原序列为：

23 45 12 78 34 67 89

这些数的个位数字依次为：

3 5 2 8 4 7 9

按照个位数字从小到大排序后，可以得到：

12 23 34 45 67 78 89

对应的个位数字为：

2 3 4 5 7 8 9

查询 (x=22)

(22) 的个位数字为 (2)。

• 第一个个位数字大于等于 (2) 的位置是 (0)；
• 第一个个位数字大于 (2) 的位置是 (1)；
• 个位数字为 (2) 的元素共有 (1) 个。

因此输出：

0 1 1

查询 (x=40)

(40) 的个位数字为 (0)。

排序后的序列中，第一个元素的个位数字为 (2)。

因此：

• 第一个个位数字大于等于 (0) 的位置是 (0)；
• 第一个个位数字大于 (0) 的位置也是 (0)；
• 个位数字为 (0) 的元素共有 (0) 个。

因此输出：

0 0 0

查询 (x=101)

(101) 的个位数字为 (1)。

虽然序列中不存在整数 (101)，但本题只比较整数的个位数字。

序列中也不存在个位数字为 (1) 的元素，因此输出：

0 0 0

---

样例输入 2

10 4
32 12 25 42 15 71 91 28 38 58
2
5
18
9

样例输出 2

2 5 3
5 7 2
7 10 3
10 10 0

---

样例解释 2

按照个位数字分类：

个位为1：71 91
个位为2：32 12 42
个位为5：25 15
个位为8：28 38 58

排序后的个位数字序列为：

1 1 2 2 2 5 5 8 8 8

对于查询 (x=2)：

• (L=2)；
• (R=5)；
• (R-L=3)。

注意，查询值 (2) 本身并没有出现在原序列中，但原序列中有三个数的个位数字为 (2)。