Tablas dispersas#691

Iniciar sesión

Enunciado Editorial Discusión

Tablas dispersas

2 segundos

128 megabytes

Difícil

Se da un arreglo de $n$ números enteros. Escriba un programa que responda consultas de la siguiente forma: encontrar el valor mínimo en el segmento desde $u$ hasta $v$ , ambos extremos incluidos.

Entrada

La primera línea contiene tres números enteros: n, m~(1 \le n \le 10^5, m \le 10^7) y a_1~(1 \le a_1 < 16714589) — la cantidad de elementos del arreglo, la cantidad de consultas y el primer elemento del arreglo, respectivamente.

La segunda línea contiene dos números enteros u_1 y v_1~(1 \le u_1, v_1 \le n), que describen la primera consulta.

Los elementos a_2, a_3, \ldots, a_n se definen mediante la siguiente fórmula:

a_{i+1} = (23 \cdot a_i + 21563) \bmod 16714589

Por ejemplo, si n = 10 y a_1 = 12345, el arreglo será:

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095)

Las consultas se generan de la siguiente manera:

u_{i+1} = ((17 \cdot u_i + 751 + ans_i + 2i) \bmod n) + 1 \\ v_{i+1} = ((13 \cdot v_i + 593 + ans_i + 5i) \bmod n) + 1

Aquí, ans_i denota la respuesta a la $i$ -ésima consulta.

Salida

Imprima u_m, v_m y ans_m — los parámetros de la última consulta y su respuesta.

Ejemplos

Ejemplo 1

Loading

Loading

n, m (1 \leq n \leq 1 0^{5}, m \leq 1 0^{7})

a_{1} (1 \leq a_{1} < 16714589)

u_{1}

v_{1} (1 \leq u_{1}, v_{1} \leq n)

a_{2}, a_{3}, \dots, a_{n}

a_{i + 1} = (23 \cdot a_{i} + 21563) mod 16714589

n = 10

a_{1} = 12345

a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095)

u_{i + 1} = ((17 \cdot u_{i} + 751 + an s_{i} + 2 i) mod n) + 1 v_{i + 1} = ((13 \cdot v_{i} + 593 + an s_{i} + 5 i) mod n) + 1

an s_{i}

u_{m}, v_{m}

an s_{m}