P10995 [MX-J3-T2] Substring

Original problem link: .

You have a sequence $a$, where each of $1 \sim n$ appears exactly once. When you choose any pair $1 \le l \le r \le n$ and write $a_l, a_{l+1}, \ldots, a_r$ in a row, you obtain a substring of $a$, denoted as $a_{l\sim r}$. Here, $l$ is called the left endpoint and $r$ is called the right endpoint. You need to sort all substrings of $a$ in lexicographical order from small to large. However, to avoid an excessively large output, I will give $q$ queries. In each query, a $k$ is given, and you need to find the left and right endpoints of the $k$-th smallest substring in lexicographical order. --- If you do not know what lexicographical order is, see here: For two sequences $p, q$, we say $p$ is lexicographically smaller than $q$ (denoted $p < q$) if and only if there exists a **natural number** $k$ such that the first $k$ numbers of $p$ and $q$ are the same, and $p_{k+1} < q_{k+1}$. In particular, if $p$ is a prefix of $q$ and $p \ne q$, then $p$ is also considered lexicographically smaller than $q$. For example: - $[1,2] < [3,2]$ (when $k = 0$). - $[3,1,100] < [3,2,1]$ (when $k = 1$). - $[3,4] < [3,4,6]$ ($p$ is a prefix of $q$).

The first line contains two positive integers $n, q$, representing the length of the sequence and the number of queries. The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, representing the sequence. Then follow $q$ lines, each containing one positive integer $k$, representing the required rank of the substring.

For each query, output one line with two integers $l, r$, indicating that the $k$-th smallest substring in lexicographical order is $a_{l\sim r}$.

**[Sample Explanation #1]** The sequence $3,1,2$ has $6$ substrings in total. After sorting from small to large, the result is: $[1], [1,2], [2], [3], [3,1], [3,1,2]$. **[Constraints]** |Test Point ID|$n \le$|$q \le$|Special Property| |:-:|:-:|:-:|:-:| |$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$|| For all testdata, it is guaranteed that $1 \le n, q \le 3\times 10^5$, $1 \le k \le \dfrac{n(n+1)}{2}$, each of $1 \sim n$ appears exactly once in $a_i$, and all inputs are integers. Translated by ChatGPT 5