Grande Muraglia (Aiuto su Segment tree)

Olimpiadi
1

Dopo aver tentato col metodo da polli con dei cicli for a destra e sinistra ho cercato di capire come funzionano i segment tree. Mi sembra di aver implementato correttamente il codice ma cmq i tasks piu facili mi danno output errato mentre i piu complessi mi vanno in TLE anche se e’ strano usando un segment tree. Quali errori riuscite a cogliere dal codice? Grazie mille in anticipo.

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector <int> segtree;
int length; // e' uguale al numero di bastioni

pair <int, int> chiedi (int index){
	
	int leftWall = -1, rightWall = 1000001;
	stack <pair <int, int> > stRange; // stack in cui memorizzo indice e valore in quella foglia
	pair <int, int> current;
	
	index += length;                    // per passare dall'indice dell'array originale all'indice del segment tree
	stRange.push({1, segtree[1]});
	
	while (!stRange.empty()){           // parto dalla radice e poi scendo giu fino alle foglie
		current = stRange.top();
		stRange.pop();
		
		if (current.second > segtree[index]){
			
			if (current.first >= length){    // se sono all'ultimo livello smetto di scendere nell'albero
				if (current.first < index && current.first > leftWall)
					leftWall = current.first;
				
				if (current.first > index && current.first < rightWall)
					rightWall = current.first; 
			} else {
				stRange.push({(2*current.first) +1, segtree[(2*current.first) +1]});
				stRange.push({2*current.first, segtree[2*current.first]});
			}
			
		}
	}
	
	// se non ho trovato nessuno bastione piu alto, stampo gli estremi dell'array
	if (leftWall == -1)
		leftWall = 0;
		
	if (rightWall == 1000001)
		rightWall = length-1;
		
	return {leftWall, rightWall};
}
void cambia (int x, int h){
    // cambiare l'indice alla foglia correlata
    x += length;
 
    // update the value at the leaf node
    // at the exact index
    segtree[x] = h;
 
    while (x > 1) {
 
        // per salire di livello nell'albero
        x /= 2;
 
        // update dei valori delle foglie 
        // nel livello piu alto
        segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
    }
}
void inizializza(int N, vector<int> H) {
	segtree = vector <int> (2*N);
	length = N;
  	for (int i = 0; i < N; i++)
        segtree[N + i] = H[i];   
 
    /* assegnare valori ai nodi interni
      per calcolare il minimo in un dato intervallo */
    for (int i = N - 1; i >= 1; i--)
        segtree[i] = max(segtree[2 * i], segtree[2 * i + 1]);
}
2

Scusate questo e’ quello “giusto” ma che va in TLE

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector <int> segtree;
int length;
pair <int, int> chiedi (int index){
	
	int leftWall = length, rightWall = 2*length-1; //imposto gli indici dei bastioni estremi
	stack <pair <int, int> > stRange;
	pair <int, int> current;
	
	index += length;
	stRange.push({1, segtree[1]});
	
	while (!stRange.empty()){
		current = stRange.top();
		stRange.pop();
		
		if (current.second > segtree[index]){
			
			if (current.first >= length){
				if (current.first < index && current.first > leftWall)
					leftWall = current.first;
				
				if (current.first > index && current.first < rightWall)
					rightWall = current.first; 
			} else {
				stRange.push({(2*current.first) +1, segtree[(2*current.first) +1]});
				stRange.push({2*current.first, segtree[2*current.first]});
			}
			
		}
	}
	leftWall -= length; // riporto gli indici all'array iniziale
	rightWall -= length;
	
	return {leftWall, rightWall};
}
void cambia (int x, int h)
{
    // change the index to leaf node first
    x += length;
 
    // update the value at the leaf node
    // at the exact index
    segtree[x] = h;
 
    while (x > 1) {
 
        // move up one level at a time in the tree
        x /= 2;
 
        // update the values in the nodes in
        // the next higher level
        segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
    }
}
void inizializza(int N, vector<int> H) {
	segtree = vector <int> (2*N);
	length = N;
  	for (int i = 0; i < N; i++)
        segtree[N + i] = H[i];   
 
    /* assign values to internal nodes
      to compute minimum in a given range */
    for (int i = N - 1; i >= 1; i--)
        segtree[i] = max(segtree[2 * i], segtree[2 * i + 1]);
        
    
}
3

Ciao, ti consiglio di consultare questo sito per saperne di più sui segment tree. Riguardo al dare qualche consiglio, non comprendo bene la tua implementazione. Potresti commentarla anche brevemente?

Buona serata :slight_smile:

4

Ciao,
Anche se non sei familiare con la ricorsione, ti consiglio di implementare almeno le query in maniera ricorsiva. Trovi degli esempi su internet ma se avessi bisogno posso mandarti del mio codice.
Altra cosa, facendo dfs iterativa, stai inserendo nello stack sempre entrambi i figli, quindi visiti tutti i nodi dell’albero ogni volta. Lo scopo del segment tree è eseguire operazioni in tempo logaritmico raggruppando informazioni e saltando quelle inutili.
Prima di provare a scrivere codice per questo problema prova a leggere e comprendere in maniera sufficientemente dettagliata come funziona un segment tree. Una volta che hai capito, prova a scriverne uno che faccia semplicemente query di somma su range e update di un elemento. Se anche quello funziona, allora scrivi questo problema.

5

Sinceramente credo di aver capito che devo ragionare a range (quindi ho sbagliato) ma quello che non capisco molto e’ come si corretta l’inizializzazione del segment tree in questo modo, perche se mi disegno a lato un array iniziale di lunghezzo diversa da una potenza di 2 i collegamenti fra i nodi vanno a forsi friggere

6

con la maniera ricorsiva mi e’ molto piu semplice la comprensione pero non so se sia efficiente richiamare sempre il vettore originale quando sto costruendo l’albero

7

Per l’aspetto della lunghezza, si tiene solitamente un array lungo 4*N e si approssima alla potenza di 2 maggiore o uguale. Nelle posizioni in più metti valori neutri (tipo 0 per la somma o infinito per il minimo)

8

Puoi passarlo per riferimento…

2 Mi Piace
9

Grazie mille per i chiarimenti, questo argomento e’ bello tosto per me :joy:

10

Se ti interessa approfondire argomenti utili per le Olimpiadi, su AlgoBadge c’è un percorso guidato che ti può essere d’aiuto (non solo per i segment tree)!

11

Dopo esser riuscito a fare query di update, somma su range, ecc… mi sono messo a fare questo ma niente da fare. adesso e’ sbagliato proprio l’output

#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
vector <int> segtree;
int length; // l'ho dichiarato perche mi serviva sapere in ogni funzione quanti bastioni ci fossere di default
int nextTwo; // potenza di 2 maggiore di length che e' piu vicina possibile a length

pair <int, int> chiedi (int index){
	
	int leftWall = 0, rightWall = length-1, mid;   // imposto gli indici tutto a destra e tutto a sinistra (gli zeri aggiunti gli escludo)
																		// nell'ultimo livello dell'albero, cioe l'array iniziale 
	stack <pair <int, pair <int, int> > > stRange;
	pair <int, pair <int, int> > current; // first = indice nell'albero; second = range di azione di quella foglia
	
	index += nextTwo;								// posizione di quel bastione nell'albero
	stRange.push({1, {0, nextTwo-1}});
	
	while (!stRange.empty()){						
		current = stRange.top();
		stRange.pop();
		
		if (segtree[current.first] > segtree[index] && ((current.second.first >= rightWall && current.second.first <= leftWall) 		// se il nodo e' maggiore del bastione di partenza o il range e' esterno ai muri left e right 
						||  (current.second.second <= leftWall && current.second.second >= rightWall))){									//allora continuo a cercare in profondita
																																																							
			if (current.first >= nextTwo){
				if (current.first < nextTwo)
					leftWall = current.second.first;
				else 
					rightWall = current.second.first;
			} 
			else {
				mid = current.second.first + (current.second.second - current.second.first)/2;
				stRange.push({2*current.first, {current.second.first, mid}});		
				stRange.push({2*current.first +1, {mid+1, current.second.second}});
				/*lo so che mi avete detto di non cercare per entrambi i figli ma non capisco come possa 
				funzionare su ne scelgo solo uno */
			}
			 
		} 
			
	}
		
	return {leftWall, rightWall};
}
void cambia (int x, int h)
{
    // change the index to leaf node first
    x += nextTwo;
 
    // update the value at the leaf node
    // at the exact index
    segtree[x] = h;
 
    while (x > 1) {
 
        // move up one level at a time in the tree
        x /= 2;
 
        // update the values in the nodes in
        // the next higher level
        segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
    }
}
void buildSegTree(vector<int>& arr, int treeIndex, int left, int right)
{
    if (left == right) {                 // leaf node. store value in node.
        if (left >= length)
        	segtree[treeIndex] = 0;
        else 
			segtree[treeIndex] = arr[left];
        return;
    }

    int mid = left + (right - left) / 2;   // recurse deeper for children.
    buildSegTree(arr, 2 * treeIndex, left, mid);
    buildSegTree(arr, 2 * treeIndex +1, mid + 1, right);

    // max build results
    segtree[treeIndex] = max(segtree[2 * treeIndex], segtree[2 * treeIndex + 1]);
}
void inizializza(int N, vector<int> H) {
	length = N;
	nextTwo = 1 << (int)ceil(log2(N));;
	
	segtree = vector <int> (2* nextTwo);
	
	buildSegTree (H, 1, 0, nextTwo-1);
}
12

Ciao, il tuo algoritmo va bene per tutto tranne che per la funzione chiedi(). Se, invece, provi con la funzione get_first() {}, che trovi alla pagina suggerita da @fabriziogiacomi, una per il bastione di sx e una per il bastione di dx ottieni facilmente 100/100.

13

Ho provato ha usare una funzione get_last per la parte di sinistra e una get_first per la parte di destra ma no funziona (la get_last l’ho fatto io modificando la get_first). Quello che non capisco è che nelle funzioni dentro agli if, in qualsiasi caso ci sara sempre un return: o -1 o lv. quindi poi come fa a fare la ricorione che viene richiamata sotto?
Allego quello che sono riuscito a fare.

#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <stack>
using namespace std;
vector <int> segtree;
int length; // l'ho dichiarato perche mi serviva sapere in ogni funzione quanti bastioni ci fossere di default
int nextTwo; // potenza di 2 maggiore di length che e' piu vicina possibile a length

int get_first(int v, int lv, int rv, int l, int r, int x) {
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(segtree[v] <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(segtree[2*v] > x) {
                v = 2*v;
                rv = mid;
            }else {
                v = 2*v+1;
                lv = mid+1;
            }
        }
        return lv;
    }

    int mid = lv + (rv-lv)/2;
    int rs = get_first(2*v, lv, mid, l, r, x);
    if(rs != -1) return rs;
    return get_first(2*v+1, mid+1, rv, l ,r, x);
}

int get_last(int v, int lv, int rv, int l, int r, int x) {
    if(lv > r || rv < l) return -1;
    if(l <= lv && rv <= r) {
        if(segtree[v] <= x) return -1;
        while(lv != rv) {
            int mid = lv + (rv-lv)/2;
            if(segtree[2*v +1] > x) {
                v = 2*v +1;
                lv = mid+1;
            }else {
                v = 2*v;
                rv = mid;
            }
        }
        return lv;
    }

    int mid = lv + (rv-lv)/2;
    int ls = get_last(2*v+1, mid+1, rv, l, r, x);
    if(ls != -1) return ls;
    return get_last(2*v, lv, mid, l ,r, x);
}

pair <int, int> chiedi (int index){
	
	int leftWall = get_last(1, 0, index-1, 0, index-1, segtree[index+nextTwo]);
	int rightWall = get_first(1, index+1, nextTwo-1, index+1, nextTwo-1, segtree[index+nextTwo]);
	
	if (leftWall == -1)
		leftWall = length-1;
		
	if (rightWall == -1)
		rightWall = 0;
		
	return {leftWall, rightWall};
}
void cambia (int x, int h)
{
    // change the index to leaf node first
    x += nextTwo;
 
    // update the value at the leaf node
    // at the exact index
    segtree[x] = h;
 
    while (x > 1) {
 
        // move up one level at a time in the tree
        x /= 2;
 
        // update the values in the nodes in
        // the next higher level
        segtree[x] = max(segtree[2 * x], segtree[2 * x + 1]);
    }
}
void buildSegTree(vector<int>& arr, int treeIndex, int left, int right)
{
    if (left == right) {                 // leaf node. store value in node.
        if (left >= length)
        	segtree[treeIndex] = 0;
        else 
			segtree[treeIndex] = arr[left];
        return;
    }

    int mid = left + (right - left) / 2;   // recurse deeper for children.
    buildSegTree(arr, 2 * treeIndex, left, mid);
    buildSegTree(arr, 2 * treeIndex +1, mid + 1, right);

    // max build results
    segtree[treeIndex] = max(segtree[2 * treeIndex], segtree[2 * treeIndex + 1]);
}
void inizializza(int N, vector<int> H) {
	length = N;
	nextTwo = 1 << (int)ceil(log2(N));;
	
	segtree = vector <int> (2* nextTwo);
	
	buildSegTree (H, 1, 0, nextTwo-1);
        
    for (int i = 0; i < 2*nextTwo; i++){
    	cout << segtree[i] << " ";
	}
    
}
14

Ora funziona tutto, non ci sto credendo!! Mi sono reso conto dopo, quando ho capito veramente come funziona, che c’erano errori un po dappertutto.
Grazie a tutti