【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$ 各有一个,输入皆为整数。