P4747 [CERC2017] Intrinsic Interval

Given a permutation $\pi$ of integers $1$ through $n$, an interval in $\pi$ is a consecutive subsequence consisting of consecutive numbers. More precisely, for indices $a$ and $b$ where $1 \le a \le b \le n$, the subsequence $\pi^b_a = (\pi_a, \pi_{a+1}, . . . ,\pi_b)$ is an interval if sorting it would yield a sequence of consecutive integers. For example, in permutation $\pi = (3, 1, 7, 5, 6, 4, 2)$, the subsequence $\pi^6_3$ is an interval (it contains the numbers $4$ through $7$) while $\pi^3_1$ is not. For a subsequence $\pi^y_x$ its intrinsic interval is any interval $\pi^b_a$ that contains the given subsequence $(a \le x \le y \le b)$ and that is, additionally, as short as possible. Of course, the length of an interval is defined as the number of elements it contains. Given a permutation $\pi$ and $m$ of its subsequences, find some intrinsic interval for each subsequence.

N/A

N/A