Máximo (Editorial)

El problema requiere responder consultas de máximo en rango. Los elementos del arreglo no cambian, por lo que una estructura de datos estática es adecuada. El número de consultas alcanza $5 \cdot 1 0^{5}$ 5 \cdot 10^5, y la longitud del arreglo es $1 0^{5}$ 10^5. Calcular el máximo de cada segmento directamente requeriría hasta $5 \cdot 1 0^{10}$ 5 \cdot 10^{10} operaciones, lo cual es demasiado lento.

Utilizamos una sparse table para el problema RMQ, pero en lugar del mínimo buscamos el máximo (Range Maximum Query). El máximo, al igual que el mínimo, no cambia si algún elemento se cuenta dos veces. Por lo tanto, el segmento de consulta puede cubrirse con dos segmentos superpuestos de longitud $2^{k}$ 2^k, y se elige el mayor de sus máximos.

Una celda de la tabla puede almacenar ya sea el índice del elemento máximo o el máximo en sí. El problema requiere imprimir solo el valor, por lo que basta con almacenar el máximo. La variante con índice es necesaria cuando se debe conocer la posición del máximo. A continuación se presentan ambas implementaciones.

Según el enunciado del problema, $1 \leq l, r \leq n$ 1 \le l, r \le n, y no se garantiza que $l \leq r$ l \le r. Por lo tanto, antes de ejecutar una consulta, intercambiamos los límites si es necesario.

Complejidad. Construir la sparse table 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 + q)$ O(n \log n + q).

Ejemplo

Consideremos el arreglo del ejemplo: $(5, 1, 2, 8, 7, 6, 10, 7, 5, 6)$ (5, 1, 2, 8, 7, 6, 10, 7, 5, 6). La tabla $ma s$ , en la cual $ma s [i] [j]$ mas[i][j] es el máximo en el segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], se muestra a continuación. 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$	$5$	$1$	$2$	$8$	$7$	$6$	$10$	$7$	$5$	$6$
$1$	$5$	$2$	$8$	$8$	$7$	$10$	$10$	$7$	$6$	—
$2$	$8$	$8$	$8$	$10$	$10$	$10$	$10$	—	—	—
$3$	$10$	$10$	$10$	—	—	—	—	—	—	—

Por ejemplo, $ma s [4] [2] = max (ma s [4] [1], ma s [6] [1]) = max (8, 10) = 10$ mas[4][2] = \max(mas[4][1], mas[6][1]) = \max(8, 10) = 10 — este es el máximo en el segmento $[4; 7]$ .

Consideremos la consulta $26$ . La longitud del segmento es $5$ , y la mayor potencia de dos que no supera $5$ es $4$ , por lo que $k = 2$ k = 2. El segmento $[2; 6]$ se cubre con los segmentos $[2; 5]$ y $[3; 6]$ , que se superponen en el segmento $[3; 5]$ :

La respuesta es $max (ma s [2] [2], ma s [3] [2]) = max (8, 8) = 8$ \max(mas[2][2], mas[3][2]) = \max(8, 8) = 8. El elemento $8$ pertenece a ambos segmentos, pero esto no afecta el valor del máximo.

Todas las consultas del ejemplo se enumeran en la tabla:

consulta	$k$	segmentos	máximos	respuesta
$110$	$3$	$[1; 8]$ , $[3; 10]$	$10, 10$	$10$
$510$	$2$	$[5; 8]$ , $[7; 10]$	$10, 10$	$10$
$15$	$2$	$[1; 4]$ , $[2; 5]$	$8, 8$	$8$
$26$	$2$	$[2; 5]$ , $[3; 6]$	$8, 8$	$8$
$23$	$1$	$[2; 3]$ , $[2; 3]$	$2, 2$	$2$
$77$	$0$	$[7; 7]$ , $[7; 7]$	$10, 10$	$10$
$78$	$1$	$[7; 8]$ , $[7; 8]$	$10, 10$	$10$
$59$	$2$	$[5; 8]$ , $[6; 9]$	$10, 10$	$10$

Para segmentos de longitud $1$ y $2$ (consultas $23$ , $77$ y $78$ ), ambos segmentos de cobertura coinciden con el propio segmento de la consulta.

Implementación del algoritmo — índice del máximo

La secuencia de entrada $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) se almacena en el arreglo $a$ comenzando desde el índice $1$ . En esta variante, la celda $ma s [i] [j]$ mas[i][j] almacena el índice del elemento máximo en el segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], y el máximo en sí es igual a $a [ma s [i] [j]]$ a[mas[i][j]]. Dado que $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, $L O GM A X = 17$ LOGMAX = 17 es suficiente para la segunda dimensión.

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

La función Build_RMQ_Array construye la sparse table de índices.

void Build_RMQ_Array()
{

Para $j = 0$ j = 0, el segmento consiste de un solo elemento, por lo que $ma s [i] [0] = i$ mas[i][0] = i.

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

Para $j > 0$ j > 0, se comparan los elementos del arreglo $a$ con í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] — los máximos en las dos mitades del segmento — y se almacena el índice del mayor.

  for (int j = 1; (1 << j) <= n; j++)
    for (int 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 RangeMaxQuery devuelve el índice del elemento máximo en el segmento $[i; j]$ .

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Si $i > j$ i > j, se intercambian los límites.

  if (i > j) temp = i, i = j, j = temp;

Luego, en un ciclo, se encuentra el mayor $k$ tal que $2^{k} \leq j - i + 1$ 2^k \le j - i + 1.

  while ((1 << (k + 1)) <= j - i + 1) k++;

Se comparan los elementos con índices $ma s [i] [k]$ mas[i][k] y $ma s [j - 2^{k} + 1] [k]$ mas[j - 2^k + 1][k] y se devuelve el índice del mayor.

  return (a[mas[i][k]] >= a[mas[j - (1 << k) + 1][k]]) ?
         mas[i][k] : mas[j - (1 << k) + 1][k];
}

Parte principal del programa. Se lee el tamaño del arreglo $n$ y sus elementos, comenzando desde el índice $1$ .

scanf("%d", &n);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

Se construye la sparse table $ma s$ a partir del arreglo $a$ .

Build_RMQ_Array();

Se lee el número de consultas $q$ .

scanf("%d", &q);

Para cada consulta, la función RangeMaxQuery devuelve el índice $in d e x$ del elemento máximo en el segmento $[u; v]$ , y se imprime el elemento $a [in d e x]$ en sí.

for (i = 0; i < q; i++)
{
  scanf("%d %d", &u, &v);
  int index = RangeMaxQuery(u, v);
  printf("%d\n", a[index]);
}

Implementación del algoritmo — máximo

La secuencia de entrada $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) se almacena en el arreglo $a$ comenzando desde el índice $1$ . En esta variante, la celda $ma s [i] [j]$ mas[i][j] almacena el máximo en sí 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}, $L O GM A X = 17$ LOGMAX = 17 es suficiente para la segunda dimensión.

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

La función Build_RMQ_Array construye la sparse table a partir del arreglo $b$ :

ma s [i] [j] = max (b [i], b [i + 1], \dots, b [i + 2^{j} - 1])

mas[i][j] = \max(b[i], b[i + 1], \ldots, b[i + 2^j - 1])

void Build_RMQ_Array(int *b)
{

Para $j = 0$ j = 0, la sparse table contiene los elementos originales del arreglo: $ma s [i] [0] = b [i]$ mas[i][0] = b[i].

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

Para $j > 0$ j > 0, el valor $ma s [i] [j]$ mas[i][j] es igual al mayor de los máximos en las dos mitades del segmento.

  for (int j = 1; 1 << j <= n; j++)
    for (int i = 1; i + (1 << j) - 1 <= n; i++)
      mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);
}

La función RangeMaxQuery devuelve el máximo en el segmento $[i; j]$ .

int RangeMaxQuery(int i, int j)
{
  int temp, k = 0;

Si $i > j$ i > j, se intercambian los límites.

  if (i > j) temp = i, i = j, j = temp;

En un ciclo, se encuentra el mayor $k$ tal que $2^{k} \leq j - i + 1$ 2^k \le j - i + 1. Esta forma de calcular $k$ no requiere la función logaritmo y no depende de errores de punto flotante.

  while ((1 << (k + 1)) <= j - i + 1) k++;

La respuesta es el mayor de los máximos en los segmentos $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] y $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

  return max(mas[i][k],mas[j - (1<<k) + 1][k]);
}

Parte principal del programa. Se lee el tamaño del arreglo $n$ y sus elementos, comenzando desde el índice $1$ .

scanf("%d",&n);
for(i = 1; i <= n; i++) scanf("%d",&a[i]);

Se construye la sparse table $ma s$ a partir del arreglo $a$ .

Build_RMQ_Array(a);

Se lee el número de consultas $q$ . Para cada consulta, se imprime el máximo en el segmento $[u; v]$ .

scanf("%d",&q);
for(i = 0; i < q; i++)
{
  scanf("%d %d",&u,&v);
  printf("%d\n",RangeMaxQuery(u,v));
}