Tablas dispersas (Editorial)

El problema requiere encontrar repetidamente el mínimo en un segmento de un arreglo que no cambia después de la generación. El número de consultas alcanza $1 0^{7}$ 10^7, por lo que cada consulta debe procesarse en $O (1)$ . Para ello, usamos una sparse table — una estructura de datos estática para el problema RMQ (Range Minimum Query, consulta de mínimo en rango).

Construcción de la tabla. Para cada posición $i$ y cada $j$ tal que $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n, la celda $ma s [i] [j]$ mas[i][j] almacena el índice del elemento mínimo en el segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] de longitud $2^{j}$ 2^j. Para $j = 0$ j = 0 el segmento consiste de un solo elemento, por lo que $ma s [i] [0] = i$ mas[i][0] = i.

Para $j > 0$ j > 0, dividimos el segmento de longitud $2^{j}$ 2^j en dos mitades de longitud $2^{j - 1}$ 2^{j-1}: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] y $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. Los índices de los mínimos en las mitades ya han sido calculados — son $ma s [i] [j - 1]$ mas[i][j - 1] y $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1]:

El mínimo de todo el segmento es igual al menor de los dos mínimos de las mitades. Por lo tanto, $ma s [i] [j]$ mas[i][j] es igual a cualquiera de los índices $ma s [i] [j - 1]$ mas[i][j - 1] y $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] que apunte al elemento más pequeño del arreglo. La tabla se completa en orden creciente de $j$ y contiene $O (n lo g n)$ O(n \log n) celdas.

Respuesta a una consulta. Supongamos que necesitamos encontrar el mínimo en el segmento $[u; v]$ . Sea $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor el exponente de la mayor potencia de dos que no excede la longitud del segmento. El segmento de longitud $2^{k}$ 2^k que comienza en $u$ y el segmento de longitud $2^{k}$ 2^k que termina en $v$ juntos cubren completamente $[u; v]$ , ya que $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

Estos segmentos pueden solaparse, pero esto no importa para el mínimo: un elemento contado dos veces no cambia el resultado (a diferencia de, por ejemplo, la suma). Por lo tanto, el mínimo en $[u; v]$ es igual al menor de los elementos $a [ma s [u] [k]]$ a[mas[u][k]] y $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]], y una consulta se procesa en $O (1)$ .

Los límites $u$ y $v$ de las consultas generadas pueden venir en cualquier orden, por lo que antes de ejecutar una consulta los intercambiamos si es necesario.

Complejidad. Construir la tabla toma $O (n lo g n)$ O(n \log n), y cada consulta toma $O (1)$ . La complejidad total es $O (n lo g n + m)$ O(n \log n + m). Con $m \leq 1 0^{7}$ m \le 10^7, es precisamente el tiempo de consulta $O (1)$ lo que permite ajustarse al límite de tiempo.

Ejemplo

Consideremos el ejemplo: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. El arreglo generado coincide con el arreglo dado en el enunciado del problema. La tabla $ma s$ para este arreglo se muestra a continuación. Las celdas contienen los índices de los elementos mínimos; un guion significa que el segmento se sale del arreglo.

$j ∖ i$ \boldsymbol{j \setminus i}	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$	$1$	$2$	$3$	$5$	$5$	$6$	$8$	$8$	$10$	—
$2$	$1$	$2$	$5$	$5$	$8$	$8$	$8$	—	—	—
$3$	$1$	$2$	$8$	—	—	—	—	—	—	—

Por ejemplo, $ma s [3] [2] = 5$ mas[3][2] = 5: en el segmento $[3; 6]$ , el elemento mínimo es $a_{5} = 1565158$ a_5 = 1565158. El valor $ma s [2] [3] = 2$ mas[2][3] = 2 se obtiene a partir de $ma s [2] [2] = 2$ mas[2][2] = 2 y $ma s [6] [2] = 8$ mas[6][2] = 8, ya que $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265.

La primera consulta: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. La longitud del segmento es $7$ , por lo que $k = 2$ k = 2. El segmento $[3; 9]$ está cubierto por los segmentos $[3; 6]$ y $[6; 9]$ , para los cuales $ma s [3] [2] = 5$ mas[3][2] = 5 y $ma s [6] [2] = 8$ mas[6][2] = 8. Dado que $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158, la respuesta es $an s_{1} = 570265$ ans_1 = 570265.

Los parámetros de la segunda consulta:

u_{2} = ((17 \cdot 3 + 751 + 570265 + 2) mod 10) + 1 = 10, v_{2} = ((13 \cdot 9 + 593 + 570265 + 5) mod 10) + 1 = 1.

u_2 = ((17 \cdot 3 + 751 + 570265 + 2) \bmod 10) + 1 = 10, \\ v_2 = ((13 \cdot 9 + 593 + 570265 + 5) \bmod 10) + 1 = 1.

Dado que $u_{2} > v_{2}$ u_2 > v_2, se intercambian los límites, y se calcula el mínimo en el segmento $[1; 10]$ .

Todas las consultas se listan en la tabla:

$i$	$u_{i}$ \boldsymbol{u_i}	$v_{i}$ \boldsymbol{v_i}	segmento	$an s_{i}$ \boldsymbol{ans_i}
$1$	$3$	$9$	$[3; 9]$	$570265$
$2$	$10$	$1$	$[1; 10]$	$12345$
$3$	$1$	$2$	$[1; 2]$	$12345$
$4$	$10$	$10$	$[10; 10]$	$1325095$
$5$	$5$	$9$	$[5; 9]$	$570265$
$6$	$2$	$1$	$[1; 2]$	$12345$
$7$	$3$	$2$	$[2; 3]$	$305498$
$8$	$5$	$3$	$[3; 5]$	$1565158$

La última consulta tiene los parámetros $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3, y su respuesta es $an s_{8} = 1565158$ ans_8 = 1565158. Estos son exactamente los valores que se imprimen. Observe que se imprimen los valores originales $u_{8}$ u_8 y $v_{8}$ v_8, no los límites ordenados del segmento.

Implementación del algoritmo

Los elementos del arreglo $a$ ( $n \leq 1 0^{5}$ n \le 10^5) se almacenan comenzando desde el índice $1$ . La sparse table se almacena en el arreglo $ma s$ : $ma s [i] [j]$ mas[i][j] es el índice del elemento mínimo en el segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1]. Dado que $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, los valores de $j$ no superan $16$ , por lo que $L O GM A X = 17$ LOGMAX = 17 es suficiente para la segunda dimensión.

#define MAX 100001
#define LOGMAX 17
int a[MAX];
int mas[MAX][LOGMAX];

La función check intercambia los valores de $u$ y $v$ si $u > v$ u > v, de modo que $u \leq v$ u \le v. Los parámetros se pasan por referencia.

void check(int &u, int &v)
{
  int temp;
  if (u > v) temp = u, u = v, v = temp;
}

La función RMQ_nlogn construye la sparse table.

void RMQ_nlogn(void)
{
  int i, j;

Primero, $ma s [i] [0] = i$ mas[i][0] = i para todo $i$ .

  for (i = 1; i <= n; i++) mas[i][0] = i;

Luego, para cada $j$ mientras $2^{j} \leq n$ 2^j \le n, y para cada $i$ tal que el segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] no se salga del arreglo, elegir entre $ma s [i] [j - 1]$ mas[i][j - 1] y $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] el índice del elemento más pequeño.

  for (j = 1; (1 << j) <= n; j++)
    for (i = 1; i + (1 << j) - 1 <= n; i++)
      if (a[mas[i][j - 1]] < a[mas[i + (1 << (j - 1))][j - 1]])
         mas[i][j] = mas[i][j - 1];
      else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];
}

La función q devuelve el índice del elemento mínimo en el segmento $[i; j]$ . Calcula $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor y compara los mínimos de dos segmentos de longitud $2^{k}$ 2^k: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] y $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

int q(int i, int j)
{
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}

C++

La parte principal del programa. Leer $n$ , $m$ , el primer elemento del arreglo $a_{1}$ a_1, y los parámetros de la primera consulta $u$ y $v$ .

scanf("%d %d",&n,&m);
scanf("%d %d %d",&a[1],&u,&v);

Generar los elementos $a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n usando la fórmula del enunciado del problema. El producto $23 \cdot a_{i}$ 23 \cdot a_i no supera $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8 y cabe en el tipo $in t$ .

for(i = 2; i <= n; i++)
  a[i] = (23 * a[i-1] + 21563) % 16714589;

Construir la sparse table $ma s$ .

RMQ_nlogn();

Procesar las $m$ consultas una por una.

for (i = 1; i <= m; i++)
{

Copiar los límites de la consulta actual en $u 1$ y $v 1$ y, si es necesario, ordenarlos con la función check. Los valores $u$ y $v$ en sí no se modifican: los parámetros de la siguiente consulta se calculan a partir de ellos, y son los que se imprimen en la respuesta.

  u1 = u; v1 = v; check(u1,v1);

Encontrar el elemento mínimo en el segmento $[u 1; v 1]$ [u1; v1].

  ans = a[q(u1,v1)];

Si la consulta no es la última, calcular los parámetros de la siguiente consulta usando las fórmulas del enunciado del problema.

  if (i < m)
  {
    u = ((17*u + 751 + ans + 2*i) % n) + 1;
    v = ((13*v + 593 + ans + 5*i) % n) + 1;
  }
}

Imprimir los parámetros de la última consulta y su respuesta.

printf("%d %d %d\n",u,v,ans);