Il capretto che ha imparato a contare (Editoriale)

Il ragazzo può scegliere due passeggeri sul segmento [l; r] se e solo se la somma delle due masse più piccole degli animali su questo segmento non supera $k$. Infatti, se una qualche coppia di animali va bene, allora la coppia formata dai due animali più leggeri va bene a maggior ragione.

Pertanto, si potrebbe costruire un segment tree in cui ogni vertice memorizza i due minimi sul proprio segmento. Tuttavia, non siamo interessati ai minimi in sé, ma solo al fatto che esistano due numeri la cui somma non superi $k$. Questo ci permette di memorizzare un solo numero in ogni vertice.

Valori nei vertici. Le foglie del segment tree memorizzano le masse degli animali. Ogni vertice interno memorizza:

• $0$ se il suo segmento contiene due animali con massa totale non superiore a $k$;

• la massa minima di un animale sul suo segmento altrimenti.

Le masse degli animali sono positive, quindi il valore $0$ non coincide con nessuna massa e indica in modo univoco che è stata trovata una coppia adatta.

Unione dei figli. Il valore di un vertice viene calcolato a partire dai valori $x$ e $y$ dei suoi figli. Una coppia adatta di animali sul segmento del vertice si trova interamente in una delle sue metà, oppure è composta da un animale della metà sinistra e un animale della metà destra. Pertanto:

• se x = 0 o y = 0, una coppia adatta si trova in una delle metà, e il valore del vertice è $0$;

• altrimenti, $x$ e $y$ sono le masse minime nelle metà, e la migliore coppia di animali provenienti da metà diverse ha una massa totale pari a x + y. Se x + y \le k, il valore del vertice è $0$, altrimenti è \min(x, y).

Con una tale funzione di unione, il problema si risolve con un segment tree standard con aggiornamenti puntuali.

Per una query di tipo $1$, la risposta è "Yes" se il valore sul segmento [l; r] è uguale a $0$, e "No" altrimenti.

Esempio

Consideriamo le query dell'esempio, k = 9. Inizialmente, le masse degli animali sono 1, 3, 1, 6, 6, 7:

• $116$: i due animali più leggeri hanno masse $1$ e $1$, 1 + 1 = 2 \le 9, la risposta è "Yes";

• $112$: 1 + 3 = 4 \le 9, la risposta è "Yes";

• $247$: la massa del quarto animale diventa $7$;

• $145$: 7 + 6 = 13 > 9, la risposta è "No";

• $156$: 6 + 7 = 13 > 9, la risposta è "No";

• $217$ e $238$: le masse del primo e del terzo animale diventano $7$ e $8$.

Prima dell'ultima query $116$, le masse degli animali sono 7, 3, 8, 7, 6, 7. Il segment tree per queste masse è mostrato di seguito. Ogni vertice mostra il proprio segmento e il valore memorizzato. Le foglie sono evidenziate in giallo, e il vertice con valore $0$ in arancione.

Calcoliamo i valori nei vertici interni:

• $[1;2]$: 7 + 3 = 10 > 9, il valore è \min(7, 3) = 3;

• $[1;3]$: 3 + 8 = 11 > 9, il valore è \min(3, 8) = 3;

• $[4;5]$: 7 + 6 = 13 > 9, il valore è \min(7, 6) = 6;

• $[4;6]$: 6 + 7 = 13 > 9, il valore è \min(6, 7) = 6;

• $[1;6]$: 3 + 6 = 9 \le 9, il valore è $0$.

Solo il vertice $[1;6]$ contiene $0$: i due animali più leggeri con masse $3$ e $6$ si trovano in metà diverse del segmento, e la loro massa totale è $9$. Pertanto, la risposta all'ultima query è "Yes".

Implementazione dell'algoritmo

Dichiariamo le costanti e gli array di lavoro. L'array SegTree memorizza il segment tree, e le masse degli animali sono memorizzate nell'array $a$. La costante $INF$ è maggiore di qualsiasi massa di un animale ed è usata come elemento neutro per un segmento vuoto. La somma di $INF$ e di qualsiasi massa non supera 2 \cdot 10^9 + 10 e rientra nel tipo $int$.

#define MAX 1000001
#define INF 1000000010
int SegTree[4 * MAX];
int a[MAX];

La funzione f unisce i valori $x$ e $y$ dei figli. Se almeno uno dei figli contiene $0$, il suo segmento contiene già due passeggeri adatti. Se x + y \le k, gli animali più leggeri delle metà sinistra e destra formano una coppia adatta. In entrambi i casi, si restituisce $0$; altrimenti, si restituisce il minimo tra $x$ e $y$.

int f(int x, int y)
{
  if (x == 0 || y == 0 || x + y <= k) return 0;
  return min(x, y);
}

La funzione BuildTree costruisce il segment tree a partire dall'array $a$. Il vertice $v$ corrisponde al segmento [lpos; rpos]. Le foglie memorizzano le masse degli animali, e i valori nei vertici interni vengono calcolati dalla funzione $f$.

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

La funzione Query restituisce il valore sul segmento [left; right]: $0$ se contiene due passeggeri con massa totale pari ad al più $k$, e la massa minima di un animale altrimenti. Il vertice $v$ corrisponde al segmento [lpos; rpos]. Per un segmento vuoto, viene restituito il valore neutro $INF$.

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

La funzione Update assegna il valore $val$ all'elemento con indice $pos$ e ricalcola i valori in tutti i vertici sul percorso dalla foglia alla radice. Il vertice $v$ corrisponde al segmento [lpos; rpos].

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] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

Parte principale del programma. Leggiamo il numero di animali $n$ e la capacità residua $k$. Leggiamo le masse degli animali nell'array $a$, a partire dall'indice $1$.

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

Costruiamo il segment tree a partire dagli elementi dell'array a[1 \ldots n].

BuildTree(1, 1, n);

Elaboriamo le $q$ query una per una. Gli animali sono numerati a partire da $1$, e anche gli elementi dell'array $a$ sono memorizzati a partire dall'indice $1$, quindi gli indici provenienti dalle query vengono usati senza modifiche.

scanf("%d", &q);
for (j = 0; j < q; j++)
{
  scanf("%d %d %d", &t, &l, &r);

Query di tipo $1$: calcoliamo il valore sul segmento [l; r]. Se è uguale a $0$, sono stati trovati due passeggeri.

  if (t == 1)
  {
    int Res = Query(1, 1, n, l, r);
    if (Res == 0) printf("Yes\n"); else printf("No\n");
  }

Query di tipo $2$: assegniamo la massa $r$ all'animale con indice $l$.

  else
    Update(1, 1, n, l, r);
}