【MX-J3-T2】Substring

题目描述

你有一个数列 $a$,**其中 $1\sim n$ 各出现了一次**。 当你任意选一对 $1\le l\le r\le n$,并将 $a_l,a_{l+1},\ldots,a_r$ 排成一行,你就得到了 $a$ 的一个子串,记为 $a_{l\sim r}$,称 $l$ 为左端点,$r$ 为右端点。 你需要把 $a$ 所有子串按字典序从小到大排序。但是为了避免输出量过大,我会给出 $q$ 个问题,每次给出一个 $k$,求字典序第 $k$ 小的子串左右端点。 --- 如果你不知道什么是字典序,看这里: 对于两个数列 $p,q$,称 $p$ 的字典序小于 $q$(记为 $p<q$),当且仅当存在**自然数** $k$ 使 $p,q$ 的前 $k$ 个数相同且 $p_{k+1}<q_{k+1}$。 特别地,若 $p$ 是 $q$ 的前缀且 $p\ne q$,也认为 $p$ 的字典序小于 $q$。 例如: - $[1,2]<[3,2]$(当 $k=0$) - $[3,1,100]<[3,2,1]$(当 $k=1$) - $[3,4]<[3,4,6]$($p$ 是 $q$ 前缀)

输入输出格式

输入格式


输入的第一行有两个正整数 $n,q$ 表示序列长度和询问个数。 第二行有 $n$ 个正整数 $a_1,a_2,\ldots,a_n$,表示这个数列。 之后有 $q$ 行,每行有一个正整数 $k$,表示要求的子串的排名。

输出格式


对于每个问题,输出一行两个整数 $l,r$,表示字典序第 $k$ 小的子串是 $a_{l\sim r}$。

输入输出样例

输入样例 #1

3 6
3 1 2
1
2
3
4
5
6

输出样例 #1

2 2
2 3
3 3
1 1
1 2
1 3

输入样例 #2

50 25
42 22 27 8 44 11 14 31 37 10 48 15 12 40 13 4 25 9 19 5 2 18 6 1 32 3 38 33 43 34 46 47 23 35 21 20 45 39 50 7 36 17 24 29 16 30 49 26 28 41
1178
991
755
1094
689
132
671
635
421
659
448
334
327
213
1206
453
1160
583
388
781
150
692
23
1162
62

输出样例 #2

37 48
27 44
3 28
1 46
43 47
20 34
33 37
2 19
15 44
2 43
7 27
6 31
6 24
4 29
32 37
7 32
5 44
19 47
13 47
44 45
23 24
43 50
24 46
5 46
26 30

说明

**【样例解释 #1】** 数列 $3,1,2$ 共有 $6$ 个子串,从小到大排序的结果为:$[1],[1,2],[2],[3],[3,1],[3,1,2]$。 **【数据范围】** |测试点编号|$n\le$|$q\le$|特殊性质| |:-:|:-:|:-:|:-:| |$1\sim 3$|$200$|$200$|| |$4\sim 7$|$1000$|$3\times 10^5$|| |$8\sim 9$|$3000$|$3\times 10^5$|| |$10\sim 13$|$3\times 10^5$|$10$|| |$14\sim 15$|$3\times 10^5$|$3\times 10^5$|$a_i=i$| |$16\sim 20$|$3\times 10^5$|$3\times 10^5$|| 对于全体数据,保证 $1\le n,q\le 3\times 10^5$,$1\le k\le \dfrac{n(n+1)}{2}$,$a_i$ 中 $1\sim n$ 各有一个,输入皆为整数。