Ciao, sto cercando di risolvere il problema con un segment tree, è la prima volta che li utilizzo e ho capito più o meno come funziona per fare la somma o trovare il valore massimo ad esemio. Credo di aver implementato bene le funzioni inizializza e cambia (correggetemi se c’è qualcosa di sbagliato), ma non so come impostare la funzione chiedi, non ci so proprio mettere mano.
#include <utility>
#include <vector>
using namespace std;
vector <int> segtree;
int segtree_size;
pair<int, int> chiedi(int x)
{
return { };
}
void cambia(int x, int h)
{
x=x+(segtree_size/2);
segtree[x]=h;
while (x>0)
{
x=(x-1)/2;
segtree[x]=max(segtree[x*2+1], segtree[x*2+2]);
}
}
void inizializza(int N, vector<int> H)
{
segtree_size=1;
while (segtree_size<N)
segtree_size=segtree_size*2;
segtree_size=segtree_size*2-1;
segtree.resize(segtree_size, 0);
for (int i=0; i<N; i++)
{
segtree[segtree_size/2+i]=H[i];
}
for (int i=segtree_size/2-1; i>=0; i--)
{
segtree[i]=max(segtree[i*2+1], segtree[i*2+2]);
}
}
Ciao, intanto pensa a un modo semplice di implementare le query in \mathcal{O}(\log^2N). Hint: puoi fare una binary search sul primo range che contiene un numero più grande di H[x]. Già così forse si riesce a farlo passare scrivendolo abbastanza bene.
Tuttavia esiste anche un modo per rispondere alle query in \mathcal{O}(\log N), per trovarlo può essere utile considerare che un range corrisponde a \mathcal{O}(\log N) nodi del segment tree, e che trovare il primo valore più maggiore di H[x] in un sottoalbero del segment si fa facilmente in \mathcal{O}(\log N) migliorando l’idea di prima.
Per la \mathcal{O}(\log^2 N), quello che vuoi fare è trovare il primo elemento maggiore di H[x] a destra di x. Sia x + k l’indice di questo elemento, allora \max H[x+1..x+\delta] \le H[x] \iff \delta < k. Fissato \delta puoi trovare Q=\max H[x+1..x+\delta] in \mathcal{O}(\log N) con una query sul segment. Ora se Q \le H[x] sai che k > \delta e viceversa quindi puoi fare una binsearch per trovare k.
Per la \mathcal{O}(\log N) quello che succede è che hai \mathcal{O}(\log N) nodi sul segment che corrispondono all’intervallo ]x, N[ (puoi provare a convincertene disegnando il segment), e a te interessa quello più a sinistra il cui massimo sia >H[x], cosa che puoi trovare in \mathcal{O}(\log N) semplicemente scorrendoli tutti. Una volta che hai trovato questo range ti interessa trovare l’elemento più a sinistra di quel range che sia >k, e questa cosa puoi farla semplicemente controllando il massimo M del figlio sinistro del nodo corrente e ricorrendo sul figlio sinistro se M>H[x] e sul figlio destro altrimenti. Quando arrivi in una foglia hai trovato l’elemento cercato.