ACM 2013 - Round #4Ended |
Estas trabajando para la compañía Macrosoft en el departamento de estructura de datos. El jefe de departamento pide que programes una estructura de dato que sea capaz de buscar el k-ésimo elemento en segmentos de una lista.
Dado una lista $a[1... N]$ de enteros diferentes, tu programa debe responder una serie de preguntas $Q(i, j, k)$ de la forma: ¿Cuál es el k-ésimo numero en el segmento $a[i... j]$, si este segmento estuviese ordenado?
Por ejemplo, considera la lista $a = (1, 5, 2, 6, 3, 7, 4)$. Sea la pregunta $Q(2, 5, 3)$. El segmento $a[2 … 5]$ es $(5, 2, 6, 3)$. Si estuviera ordenado, tendríamos $(2, 3, 5, 6)$, el tercer elemento es $5$ y por tanto la respuesta a la pregunta anterior seria $5$.
La primera línea de la entrada contiene a $N$ – el tamaño de la lista, y $M$ – el número de preguntas a responder $(1 \leq N \leq 100000, 1 \leq M \leq 5000)$.
La segunda línea contiene $N$ enteros diferentes que no exceden $10^9$ por su valor absoluto – la descripción de la lista.
Las siguientes $M$ líneas contienen la descripción de las preguntas, cada descripción consiste de tres números $i$, $j$ y $k$ $(1 \leq i \leq j \leq N, 1 \leq k \leq j - i + 1)$ y representan la pregunta $Q(i, j, k)$.
Por cada pregunta la respuesta correspondiente – el k-ésimo número en el segmento ordenado $a[i ... j]$.