Massimo (Editoriale)

Il problema richiede di rispondere a query di massimo su intervallo. Gli elementi dell'array non cambiano, quindi è adatta una struttura dati statica. Il numero di query arriva a $5 \cdot 1 0^{5}$ 5 \cdot 10^5, e la lunghezza dell'array è $1 0^{5}$ 10^5. Calcolare il massimo di ogni segmento direttamente richiederebbe fino a $5 \cdot 1 0^{10}$ 5 \cdot 10^{10} operazioni, il che è troppo lento.

Utilizziamo una sparse table per il problema RMQ, ma invece del minimo cerchiamo il massimo (Range Maximum Query). Il massimo, come il minimo, non cambia se qualche elemento viene contato due volte. Pertanto, il segmento della query può essere coperto da due segmenti sovrapposti di lunghezza $2^{k}$ 2^k, e viene scelto il maggiore tra i loro massimi.

Una cella della tabella può memorizzare sia l'indice dell'elemento massimo che il massimo stesso. Il problema richiede di stampare solo il valore, quindi è sufficiente memorizzare il massimo. La variante con l'indice è necessaria quando serve conoscere la posizione del massimo. Di seguito sono fornite entrambe le implementazioni.

Secondo il testo del problema, $1 \leq l, r \leq n$ 1 \le l, r \le n, e non è garantito che $l \leq r$ l \le r. Pertanto, prima di eseguire una query, scambiamo gli estremi se necessario.

Complessità. Costruire la sparse table richiede $O (n lo g n)$ O(n \log n), e ogni query richiede $O (1)$ . La complessità complessiva è $O (n lo g n + q)$ O(n \log n + q).

Esempio

Consideriamo l'array dell'esempio: $(5, 1, 2, 8, 7, 6, 10, 7, 5, 6)$ (5, 1, 2, 8, 7, 6, 10, 7, 5, 6). La tabella $ma s$ , in cui $ma s [i] [j]$ mas[i][j] è il massimo sul segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], è mostrata sotto. Un trattino indica che il segmento va oltre i limiti dell'array.

$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$	—	—	—	—	—	—	—

Ad esempio, $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 — questo è il massimo sul segmento $[4; 7]$ .

Consideriamo la query $26$ . La lunghezza del segmento è $5$ , e la più grande potenza di due non superiore a $5$ è $4$ , quindi $k = 2$ k = 2. Il segmento $[2; 6]$ è coperto dai segmenti $[2; 5]$ e $[3; 6]$ , che si sovrappongono sul segmento $[3; 5]$ :

La risposta è $max (ma s [2] [2], ma s [3] [2]) = max (8, 8) = 8$ \max(mas[2][2], mas[3][2]) = \max(8, 8) = 8. L'elemento $8$ appartiene a entrambi i segmenti, ma ciò non influisce sul valore del massimo.

Tutte le query dell'esempio sono elencate nella tabella:

query	$k$	segmenti	massimi	risposta
$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$

Per segmenti di lunghezza $1$ e $2$ (query $23$ , $77$ e $78$ ), entrambi i segmenti di copertura coincidono con il segmento della query stesso.

Implementazione dell'algoritmo — indice del massimo

La sequenza in ingresso $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) è memorizzata nell'array $a$ a partire dall'indice $1$ . In questa variante, la cella $ma s [i] [j]$ mas[i][j] memorizza l'indice dell'elemento massimo sul segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1], e il massimo stesso è pari ad $a [ma s [i] [j]]$ a[mas[i][j]]. Poiché $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, $L O GM A X = 17$ LOGMAX = 17 è sufficiente per la seconda dimensione.

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

La funzione Build_RMQ_Array costruisce la sparse table degli indici.

void Build_RMQ_Array()
{

Per $j = 0$ j = 0, il segmento è composto da un solo elemento, quindi $ma s [i] [0] = i$ mas[i][0] = i.

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

Per $j > 0$ j > 0, si confrontano gli elementi dell'array $a$ con indici $ma s [i] [j - 1]$ mas[i][j - 1] e $ma s [i + 2^{j - 1}] [j - 1]$ mas[i + 2^{j-1}][j - 1] — i massimi sulle due metà del segmento — e si memorizza l'indice del maggiore.

  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 funzione RangeMaxQuery restituisce l'indice dell'elemento massimo sul segmento $[i; j]$ .

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

Se $i > j$ i > j, gli estremi vengono scambiati.

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

Quindi, in un ciclo, si trova il più grande $k$ tale che $2^{k} \leq j - i + 1$ 2^k \le j - i + 1.

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

Si confrontano gli elementi con indici $ma s [i] [k]$ mas[i][k] e $ma s [j - 2^{k} + 1] [k]$ mas[j - 2^k + 1][k] e si restituisce l'indice del maggiore.

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

La parte principale del programma. Si leggono la dimensione dell'array $n$ e i suoi elementi, a partire dall'indice $1$ .

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

Si costruisce la sparse table $ma s$ a partire dall'array $a$ .

Build_RMQ_Array();

Si legge il numero di query $q$ .

scanf("%d", &q);

Per ogni query, la funzione RangeMaxQuery restituisce l'indice $in d e x$ dell'elemento massimo sul segmento $[u; v]$ , e stampiamo l'elemento $a [in d e x]$ stesso.

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

Implementazione dell'algoritmo — massimo

La sequenza in ingresso $a_{i}$ a_i ( $n \leq 1 0^{5}$ n \le 10^5) è memorizzata nell'array $a$ a partire dall'indice $1$ . In questa variante, la cella $ma s [i] [j]$ mas[i][j] memorizza il massimo stesso sul segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1]. Poiché $2^{16} \leq 1 0^{5} < 2^{17}$ 2^{16} \le 10^5 < 2^{17}, $L O GM A X = 17$ LOGMAX = 17 è sufficiente per la seconda dimensione.

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

La funzione Build_RMQ_Array costruisce la sparse table a partire dall'array $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)
{

Per $j = 0$ j = 0, la sparse table contiene gli elementi dell'array originale: $ma s [i] [0] = b [i]$ mas[i][0] = b[i].

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

Per $j > 0$ j > 0, il valore $ma s [i] [j]$ mas[i][j] è pari al maggiore tra i massimi sulle due metà 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 funzione RangeMaxQuery restituisce il massimo sul segmento $[i; j]$ .

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

Se $i > j$ i > j, gli estremi vengono scambiati.

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

In un ciclo, si trova il più grande $k$ tale che $2^{k} \leq j - i + 1$ 2^k \le j - i + 1. Questo modo di calcolare $k$ non richiede la funzione logaritmo e non dipende da errori in virgola mobile.

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

La risposta è il maggiore tra i massimi sui segmenti $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] e $[j - 2^{k} + 1; j]$ [j - 2^k + 1; j].

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

La parte principale del programma. Si leggono la dimensione dell'array $n$ e i suoi elementi, a partire dall'indice $1$ .

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

Si costruisce la sparse table $ma s$ a partire dall'array $a$ .

Build_RMQ_Array(a);

Si legge il numero di query $q$ . Per ogni query, si stampa il massimo sul segmento $[u; v]$ .

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