Sto provando ad imparare ad implementare un segtree, e ho deciso di cimentarmi nell’omonimo problema. Purtroppo la mia soluzione (oltre ad andare in timeout, ma quello è perchè non sto facendo lazy propagation), sbaglia i primi due testcase del subtask 6, e non riesco a capire perchè…
L’unica cosa che cambia tra i testcase dei subtask precedenti e il subtask 6 è che nell’ultimo il grader può utilizzare la funzione lower_bound, mentre negli altri no…
Questo è il codice:
#include <bits/stdc++.h>
using namespace std;
// Valori neutri rispettivamente per somma e minimo.
const long long NEUTRO = 0;
const long long NEUTRO_MIN = LLONG_MAX;
struct Nodo {
long long val;
long long mi;
Nodo() : val(NEUTRO), mi(NEUTRO_MIN) {};
// Nodo tiene valore della somma e minimo.
void join(Nodo &a, Nodo &b) {
val = a.val + b.val;
mi = min(a.mi, b.mi);
}
};
int n, realSize;
vector<Nodo> segTree;
void build(int u, int l, int r, vector<long long> &dati);
void init(vector<long long> a) {
n = a.size();
realSize = 1;
while (realSize < n) {
// grandezza del vettore deve essere una potenza di due.
realSize *= 2;
}
// prima metà si tiene l'albero binario, seconda metà i dati.
segTree.assign(realSize * 2, Nodo());
build(1, 0, realSize, a);
}
void build(int u, int l, int r, vector<long long> &dati) {
if (r - l <= 1) {
// Sono una foglia, quindi imposto il valore direttamente
// Se elemento è effettivamente un elemento, essendo dati non per forza una potenza di 2
if (l < dati.size()) {
segTree[u].val = dati[l];
segTree[u].mi = dati[l];
}
} else {
// Non sono una foglia, ricorro...
build(u * 2, l, (l + r)/2, dati);
build((u * 2) + 1, (l + r)/2, r, dati);
// joino i risultati
segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
}
}
long long get_min(int u, int left, int right, int l, int r) {
if (left >= l && right <= r) {
// Mi piace, mi fermo quì
return segTree[u].mi;
}
if (r <= left || l >= right) {
// Non compreso nel mio insieme. Mi fermo quì!
return NEUTRO_MIN;
}
// Devo ricorrere 😭
return min(
get_min(u * 2, left, (left + right) / 2, l, r),
get_min((u * 2) + 1, (left + right) / 2, right, l, r)
);
}
long long get_sum(int u, int left, int right, int l, int r) {
if (left >= l && right <= r) {
// Mi piace, mi fermo quì
return segTree[u].val;
}
if (r <= left || l >= right) {
// Non compreso nel mio insieme. Mi fermo quì!
return NEUTRO;
}
// Devo ricorrere 😭
return (
get_sum(u * 2, left, (left + right) / 2, l, r) +
get_sum((u * 2) + 1, (left + right) / 2, right, l, r)
);
}
long long get_min(int l, int r) {return get_min(1, 0, realSize, l, r); }
long long get_sum(int l, int r) {return get_sum(1, 0, realSize, l, r); }
void set_range(int u, int left, int right, int l, int r, int x) {
if (l >= right || r <= left) return;
if (right - left <= 1) {
// Sono una foglia, quindi imposto il valore direttamente
segTree[u].val = x;
segTree[u].mi = x;
} else {
// Non sono una foglia, ricorro...
set_range(u * 2, left, (left + right)/2, l, r, x);
set_range((u * 2) + 1, (left + right)/2, right, l, r, x);
// joino i risultati
segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
}
}
void set_range(int l, int r, long long x) {set_range(1, 0, realSize, l, r, x);}
void add(int u, int left, int right, int l, int r, int x) {
if (l >= right || r <= left) return;
if (right - left <= 1) {
// Sono una foglia, quindi imposto il valore direttamente
segTree[u].val += x;
segTree[u].mi += x;
} else {
// Non sono una foglia, ricorro...
add(u * 2, left, (left + right)/2, l, r, x);
add((u * 2) + 1, (left + right)/2, right, l, r, x);
// joino i risultati
segTree[u].join(segTree[u * 2], segTree[u * 2 + 1]);
}
}
void add(int l, int r, long long x) {add(1, 0, realSize, l, r, x);}
int lower_bound(int u, int left, int right, int l, int r, long long x) {
if (right - left <= 1) {
// Sono una foglia, ritorno l'indice 😁
return u - realSize;
}
// Ricorro... 😭
int mi = 0;
// Controllo se right e left sono in range
if (left < r && (right + left) / 2 > l) {
// left è in range
int left = segTree[u * 2].mi;
if (left < x && left < segTree[mi].mi) {
mi = u * 2;
}
}
if ((left + right) / 2 < r && right > l) {
// right è in range
int right = segTree[(u * 2) + 1].mi;
if (right < x && right < segTree[mi].mi) {
mi = (u * 2) + 1;
}
}
// Non esiste
if (mi == 0) return -1;
else if (mi == u * 2) {
// Vado a sinistra
return lower_bound(mi, left, (left + right) / 2, l, r, x);
}
// Vado a destra.
return lower_bound(mi, (left + right) / 2, right, l, r, x);
}
int lower_bound(int l, int r, long long x) {
return lower_bound(1, 0, realSize, l, r, x);
}