Tabelle sparse (Editoriale)

Il problema richiede di trovare ripetutamente il minimo su un segmento di un array che non cambia dopo la generazione. Il numero di query arriva fino a $1 0^{7}$ 10^7, quindi ogni query deve essere elaborata in $O (1)$ . Per fare ciò, utilizziamo una sparse table — una struttura dati statica per il problema RMQ (Range Minimum Query).

Costruzione della tabella. Per ogni posizione $i$ e ogni $j$ tale che $i + 2^{j} - 1 \leq n$ i + 2^j - 1 \le n, la cella $ma s [i] [j]$ mas[i][j] memorizza l'indice dell'elemento minimo sul segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] di lunghezza $2^{j}$ 2^j. Per $j = 0$ j = 0 il segmento è costituito da un solo elemento, quindi $ma s [i] [0] = i$ mas[i][0] = i.

Per $j > 0$ j > 0, dividiamo il segmento di lunghezza $2^{j}$ 2^j in due metà di lunghezza $2^{j - 1}$ 2^{j-1}: $[i; i + 2^{j - 1} - 1]$ [i; i + 2^{j-1} - 1] e $[i + 2^{j - 1}; i + 2^{j} - 1]$ [i + 2^{j-1}; i + 2^j - 1]. Gli indici dei minimi sulle due metà sono già stati calcolati — sono $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]:

Il minimo dell'intero segmento è uguale al più piccolo dei due minimi delle metà. Pertanto, $ma s [i] [j]$ mas[i][j] è uguale a quale dei due 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] punta all'elemento più piccolo dell'array. La tabella viene riempita in ordine crescente di $j$ e contiene $O (n lo g n)$ O(n \log n) celle.

Risposta a una query. Supponiamo di dover trovare il minimo sul segmento $[u; v]$ . Sia $k = ⌊ lo g_{2} (v - u + 1)⌋$ k = \lfloor \log_2(v - u + 1) \rfloor l'esponente della più grande potenza di due che non supera la lunghezza del segmento. Il segmento di lunghezza $2^{k}$ 2^k che inizia in $u$ e il segmento di lunghezza $2^{k}$ 2^k che termina in $v$ coprono insieme completamente $[u; v]$ , poiché $2 \cdot 2^{k} > v - u + 1$ 2 \cdot 2^k > v - u + 1:

Questi segmenti possono sovrapporsi, ma ciò non ha importanza per il minimo: un elemento contato due volte non cambia il risultato (a differenza, ad esempio, della somma). Pertanto, il minimo su $[u; v]$ è uguale al più piccolo tra gli elementi $a [ma s [u] [k]]$ a[mas[u][k]] e $a [ma s [v - 2^{k} + 1] [k]]$ a[mas[v - 2^k + 1][k]], e una query viene elaborata in $O (1)$ .

Gli estremi $u$ e $v$ delle query generate possono comparire in qualsiasi ordine, quindi prima di eseguire una query li scambiamo se necessario.

Complessità. La costruzione della tabella richiede $O (n lo g n)$ O(n \log n), e ogni query richiede $O (1)$ . La complessità complessiva è $O (n lo g n + m)$ O(n \log n + m). Con $m \leq 1 0^{7}$ m \le 10^7, è proprio il tempo di query $O (1)$ a rendere possibile rientrare nel limite di tempo.

Esempio

Consideriamo l'esempio: $n = 10$ n = 10, $m = 8$ m = 8, $a_{1} = 12345$ a_1 = 12345. L'array generato coincide con l'array fornito nell'enunciato del problema. La tabella $ma s$ per esso è mostrata di seguito. Le celle contengono gli indici degli elementi minimi; 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$	$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$	—	—	—	—	—	—	—

Ad esempio, $ma s [3] [2] = 5$ mas[3][2] = 5: sul segmento $[3; 6]$ , l'elemento minimo è $a_{5} = 1565158$ a_5 = 1565158. Il valore $ma s [2] [3] = 2$ mas[2][3] = 2 si ottiene da $ma s [2] [2] = 2$ mas[2][2] = 2 e $ma s [6] [2] = 8$ mas[6][2] = 8, poiché $a_{2} = 305498 < a_{8} = 570265$ a_2 = 305498 < a_8 = 570265.

La prima query: $u_{1} = 3$ u_1 = 3, $v_{1} = 9$ v_1 = 9. La lunghezza del segmento è $7$ , quindi $k = 2$ k = 2. Il segmento $[3; 9]$ è coperto dai segmenti $[3; 6]$ e $[6; 9]$ , per i quali $ma s [3] [2] = 5$ mas[3][2] = 5 e $ma s [6] [2] = 8$ mas[6][2] = 8. Poiché $a_{8} = 570265 < a_{5} = 1565158$ a_8 = 570265 < a_5 = 1565158, la risposta è $an s_{1} = 570265$ ans_1 = 570265.

I parametri della seconda query:

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.

Poiché $u_{2} > v_{2}$ u_2 > v_2, gli estremi vengono scambiati, e viene calcolato il minimo sul segmento $[1; 10]$ .

Tutte le query sono elencate nella tabella:

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

L'ultima query ha i parametri $u_{8} = 5$ u_8 = 5, $v_{8} = 3$ v_8 = 3, e la sua risposta è $an s_{8} = 1565158$ ans_8 = 1565158. Questi sono esattamente i valori che vengono stampati. Si noti che vengono stampati i valori originali $u_{8}$ u_8 e $v_{8}$ v_8, non gli estremi ordinati del segmento.

Implementazione dell'algoritmo

Gli elementi dell'array $a$ ( $n \leq 1 0^{5}$ n \le 10^5) sono memorizzati a partire dall'indice $1$ . La sparse table è memorizzata nell'array $ma s$ : $ma s [i] [j]$ mas[i][j] è l'indice dell'elemento minimo 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}, i valori di $j$ non superano $16$ , quindi $L O GM A X = 17$ LOGMAX = 17 è sufficiente per la seconda dimensione.

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

La funzione check scambia i valori di $u$ e $v$ se $u > v$ u > v, in modo che $u \leq v$ u \le v. I parametri vengono passati per riferimento.

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

La funzione RMQ_nlogn costruisce la sparse table.

void RMQ_nlogn(void)
{
  int i, j;

Prima di tutto, $ma s [i] [0] = i$ mas[i][0] = i per tutti gli $i$ .

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

Poi, per ogni $j$ finché $2^{j} \leq n$ 2^j \le n, e per ogni $i$ tale che il segmento $[i; i + 2^{j} - 1]$ [i; i + 2^j - 1] non vada oltre i limiti dell'array, si sceglie tra $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] l'indice dell'elemento più piccolo.

  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 funzione q restituisce l'indice dell'elemento minimo sul segmento $[i; j]$ . Si calcola $k = ⌊ lo g_{2} (j - i + 1)⌋$ k = \lfloor \log_2(j - i + 1) \rfloor e si confrontano i minimi di due segmenti di lunghezza $2^{k}$ 2^k: $[i; i + 2^{k} - 1]$ [i; i + 2^k - 1] e $[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 principale del programma. Si leggono $n$ , $m$ , il primo elemento dell'array $a_{1}$ a_1 e i parametri della prima query $u$ e $v$ .

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

Si generano gli elementi $a_{2}, a_{3}, \dots, a_{n}$ a_2, a_3, \ldots, a_n utilizzando la formula dell'enunciato. Il prodotto $23 \cdot a_{i}$ 23 \cdot a_i non supera $23 \cdot 16714589 \approx 3.8 \cdot 1 0^{8}$ 23 \cdot 16714589 \approx 3.8 \cdot 10^8 e rientra nel tipo $in t$ .

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

Si costruisce la sparse table $ma s$ .

RMQ_nlogn();

Si elaborano le $m$ query una per una.

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

Si copiano gli estremi della query corrente in $u 1$ e $v 1$ e, se necessario, li si ordina con la funzione check. I valori $u$ e $v$ stessi non vengono modificati: da essi vengono calcolati i parametri della query successiva, e sono quelli che vengono stampati nella risposta.

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

Si trova l'elemento minimo sul segmento $[u 1; v 1]$ [u1; v1].

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

Se la query non è l'ultima, si calcolano i parametri della query successiva utilizzando le formule dell'enunciato.

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

Si stampano i parametri dell'ultima query e la sua risposta.

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