Nel paese delle lezioni non apprese#4481

Nel paese delle lezioni non apprese (Editoriale)

Per risolvere il problema, dobbiamo elaborare query di due tipi:

calcolare il massimo comune divisore (MCD) degli elementi su un segmento;
modificare un elemento dell'array.

La proprietà chiave del MCD è la sua associatività: il MCD di più numeri può essere calcolato a pezzi. Se il segmento $[l, r]$ [l, r] viene diviso in due parti $[l, k]$ [l, k] e $[k + 1, r]$ [k + 1, r], allora

GCD (a_{l}, \dots, a_{r}) = GCD (GCD (a_{l}, \dots, a_{k}), GCD (a_{k + 1}, \dots, a_{r}))

\mathrm{GCD}(a_l, \ldots, a_r) = \mathrm{GCD}(\mathrm{GCD}(a_l, \ldots, a_k), \mathrm{GCD}(a_{k+1}, \ldots, a_r))

Questo è esattamente il tipo di operazione per cui è progettato un albero dei segmenti (segment tree). Ogni vertice memorizza il MCD degli elementi del proprio segmento, e il valore in un vertice interno è uguale al MCD dei valori dei suoi due figli. L'albero dei segmenti permette sia di calcolare il MCD su un segmento sia di modificare un elemento dell'array utilizzando $O (lo g n)$ O(\log n) operazioni di MCD.

Esempio

Vediamo come funziona l'algoritmo sull'esempio. La figura a sinistra mostra l'albero dei segmenti per l'array iniziale $(2, 4, 6, 10, 8)$ (2, 4, 6, 10, 8). Ogni vertice mostra il proprio segmento e il MCD degli elementi su di esso. La figura a destra mostra l'albero dopo l'esecuzione di entrambe le query di aggiornamento; i vertici i cui valori sono cambiati sono evidenziati.

Elaboriamo le query una per una:

$115$ : il segmento $[1, 5]$ coincide con il segmento della radice, quindi la risposta è memorizzata nella radice ed è uguale a $2$ ;
$123$ : il segmento $[2, 3]$ viene diviso nelle parti $[2]$ e $[3]$ , la risposta è $GCD (4, 6) = 2$ \mathrm{GCD}(4, 6) = 2;
$2515$ : l'elemento $a_{5}$ a_5 diventa $15$ . I vertici sul percorso dalla foglia $[5]$ alla radice vengono ricalcolati: nel vertice $[4, 5]$ otteniamo $GCD (10, 15) = 5$ \mathrm{GCD}(10, 15) = 5, nella radice — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$2310$ : l'elemento $a_{3}$ a_3 diventa $10$ . Nel vertice $[1, 3]$ otteniamo $GCD (2, 10) = 2$ \mathrm{GCD}(2, 10) = 2, nella radice — $GCD (2, 5) = 1$ \mathrm{GCD}(2, 5) = 1;
$135$ : il segmento $[3, 5]$ viene diviso nelle parti $[3]$ e $[4, 5]$ , la risposta è $GCD (10, 5) = 5$ \mathrm{GCD}(10, 5) = 5;
$115$ : la risposta è memorizzata nella radice ed è uguale a $1$ .

Otteniamo le risposte $2, 2, 5, 1$ 2, 2, 5, 1, che coincidono con la risposta dell'esempio.

Implementazione dell'algoritmo

Dichiariamo l'array $S e g T r ee$ SegTree per memorizzare l'albero dei segmenti e l'array $v$ per memorizzare la sequenza di numeri in input. Ogni vertice dell'albero memorizza il MCD degli elementi del proprio segmento. Poiché $a_{i} \leq 1 0^{9}$ a_i \le 10^9 e il MCD non supera i suoi argomenti, i valori nelle celle di $S e g T r ee$ SegTree non superano i limiti del tipo int.

vector<int> SegTree, v;

La funzione BuildTree costruisce l'albero dei segmenti a partire dall'array $a$ . Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos]. Viene utilizzata la funzione standard $g c d$ per calcolare il MCD di due numeri.

void BuildTree(vector<int> &a, int v, int lpos, int rpos)
{
  if (lpos == rpos) SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(a, 2 * v, lpos, mid);
    BuildTree(a, 2 * v + 1, mid + 1, rpos);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

La funzione GetGCD restituisce il MCD degli elementi sul segmento $[l e f t, r i g h t]$ [left, right]. Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos].

Se il segmento della query è vuoto ( $l e f t > r i g h t$ left > right), restituire $0$ — l'elemento neutro per l'operazione di MCD. Se il segmento della query coincide con il segmento del vertice, la risposta è memorizzata in $S e g T r ee [v]$ SegTree[v]. Altrimenti, dividere la query nelle parti che ricadono nel figlio sinistro e in quello destro, e restituire il MCD dei risultati.

int GetGCD(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return 0;
  if ((left == lpos) && (right == rpos)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
         GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

C++

La funzione update assegna il valore $v a l$ all'elemento con indice $p os$ . Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos].

Scendere fino alla foglia corrispondente alla posizione $p os$ e scrivervi il nuovo valore. Durante il ritorno dalla ricorsione, ricalcolare il MCD in tutti i vertici sul percorso dalla foglia alla radice.

void update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos) SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) update(2 * v, lpos, mid, pos, val);
    else update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

C++

La parte principale del programma. Leggiamo la sequenza di numeri in input nell'array $v$ , a partire dall'indice $1$ .

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

Costruiamo l'albero dei segmenti a partire dagli elementi dell'array $v [1 \dots n]$ v[1 \ldots n]. Un albero dei segmenti su $n$ elementi necessita al massimo di $4 n$ celle.

SegTree.resize(4 * n);
BuildTree(v,1,1,n);

Elaboriamo le query una per una. Se $q = 1$ q = 1, stampiamo il MCD sul segmento $[l, r]$ [l, r]. Se $q = 2$ q = 2, assegniamo il valore $r$ all'elemento con indice $l$ .

scanf("%d",&m);
for(i = 0; i < m; i++)
{
  scanf("%d %d %d",&q,&l,&r);
  if (q == 1) printf("%d\n",GetGCD(1,1,n,l,r));
  else update(1,1,n,l,r);
}

C++

Implementazione in Python

La lista $S e g T r ee$ SegTree memorizza l'albero dei segmenti; ciascuno dei suoi vertici contiene il MCD degli elementi del proprio segmento. Importiamo il modulo $ma t h$ , che contiene una funzione per calcolare il MCD.

import math

Dichiariamo la funzione gcd, che calcola il MCD di due numeri.

def gcd(a, b):
  return math.gcd(a, b)

La funzione BuildTree costruisce l'albero dei segmenti a partire dalla lista $a$ . Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos].

def BuildTree(a, v, lpos, rpos):
  if lpos == rpos:
    SegTree[v] = a[lpos]
  else:
    mid = (lpos + rpos) // 2
    BuildTree(a, 2 * v, lpos, mid)
    BuildTree(a, 2 * v + 1, mid + 1, rpos)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

La funzione GetGCD restituisce il MCD degli elementi sul segmento $[l e f t, r i g h t]$ [left, right]. Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos].

def GetGCD(v, lpos, rpos, left, right):
  if left > right:
    return 0
  if left == lpos and right == rpos:
    return SegTree[v]
  mid = (lpos + rpos) // 2
  return gcd(GetGCD(2 * v, lpos, mid, left, min(right, mid)),
      GetGCD(2 * v + 1, mid + 1, rpos, max(left, mid + 1),right))

Python

La funzione Update assegna il valore $v a l$ all'elemento con indice $p os$ . Il vertice $v$ corrisponde al segmento $[l p os, r p os]$ [lpos, rpos].

def Update(v, lpos, rpos, pos, val):
  if lpos == rpos:
    SegTree[v] = val
  else:
    mid = (lpos + rpos) // 2
    if pos <= mid:
      Update(2 * v, lpos, mid, pos, val)
    else:
      Update(2 * v + 1, mid + 1, rpos, pos, val)
    SegTree[v] = gcd(SegTree[2 * v], SegTree[2 * v + 1])

Python

La parte principale del programma. Leggiamo la sequenza di numeri in input nella lista $v$ , a partire dall'indice $1$ .

n = int(input())
v = [0] + list(map(int, input().split()))

Costruiamo l'albero dei segmenti a partire dagli elementi della lista $v [1 \dots n]$ v[1 \ldots n]. Un albero dei segmenti su $n$ elementi necessita al massimo di $4 n$ celle.

SegTree = [0] * (4 * n)
BuildTree(v, 1, 1, n)

Elaboriamo le query una per una. Se $q = 1$ q = 1, stampiamo il MCD sul segmento $[l, r]$ [l, r]; se $q = 2$ q = 2, assegniamo il valore $r$ all'elemento con indice $l$ .

m = int(input())
for _ in range(m):
  q, l, r = map(int, input().split())
  if q == 1:
    print(GetGCD(1, 1, n, l, r))
  else:
    Update(1, 1, n, l, r)

Python