# Muraglia (ST) help

**URL:** <https://forum.olinfo.it/t/muraglia-st-help/8350>\
**Category:** Aiuto\
**Created:** [24 Giugno 2023, 3:30pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350 "2023-06-24T15:30:21Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [24 Giugno 2023, 3:30pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/1 "2023-06-24T15:30:21Z")

</div>

Salve a tutti, sto provando a risolvere muraglia da qualche giorno e sono riuscito (almeno penso) a creare correttamente il segment tree e a sviluppare la funzione update però non riesco a creare la funzione chiedi.  
Ho seguito il consiglio di usare la funzione _get\_first_ su [questo sito](https://cp-algorithms.com/data_structures/segment_tree.html) ma non ottengo i valori che cerco e in generale non so interpretarli perché non mi è molto chiaro cosa fa questa funzione.  
Ecco il codice fin’ora:

```auto
#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
void build(int u, int sx, int dx, vector<int> data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
	size = 1;
	
    while(size < N)
        size *= 2;
    nodes.assign(2*size, -1); // totale nodi=2*N-1
    build(1, 0, size, data);
}
void cambia(int x, int h){
	int p = size + x; //size è il primo del vector
	nodes[p] = h;
	while(p>1){
		p/=2; //risalgo
		nodes[p] = max(nodes[2*p], nodes[2*p+1]);
	}
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
	if(sx > b or dx < a) return -1;
	if(a <= sx and dx <= b){
		if(nodes[pos] <= x)	return -1;
		while(sx != dx){
			int m = sx + (dx-sx)/2;
			if(nodes[2*pos] > x){ 
				pos = 2*pos;
				dx = m; 
			}
			else{
				pos = 2*pos+1;
				sx = m+1;
			}
		}
		return sx;
	}
	int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
//pair<int, int> 
int chiedi(int x){
	int pos = succ(1, x+1, 2*size, x+1, 2*size, x);
	return pos;
}
int main(){
    int N = 14;
    vector<int> data = {7, 4, 78, 2, 6, 4, 1, 9, 10, 7, 100, 56, 8, 1};
    inizializza(N, data);
    for(int i=1; i<nodes.size(); i++){ //stampo il ST
        if(i==2 or i==4 or i==8 or i==16) cout<<"\n";
        cout<<nodes[i]<<"\t";
    }
    cambia(7, 3);	//test update
    cout<<"\n\n";
    cout<<chiedi(1)<<endl; //test chiedi
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [25 Giugno 2023, 4:09pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/2 "2023-06-25T16:09:34Z")

</div>

Ciao, la funzione:

int succ(int pos, int sx, int dx, int a, int b, int x) {}

restituisce la possizione p della torre nell’intervallo [a,b] che soddisfa la condizione data[p] \> x, se non la trova return -1.  
Quelli che non sono corretti sono i valori che passi in :

int chiedi(int x) {  
int pos = succ(1, x+1, 2_size, x+1, 2_size, x);  
return pos;  
}

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [27 Giugno 2023, 6:48pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/3 "2023-06-27T18:48:54Z")

</div>

Ciao, ho provato ha inserire vari valori nella chiamata ma non ottengo mai l’output corretto.

```auto
int pos = succ(1, size+x+1, 2*size, size+x+1, 2*size, nodes[x + size]);

```

Di sicuro dovevo inserire la size perché sto lavorando nel ST e non nell’array, poi il mio ragionamento è che la funzione parte dalla radice perché pos raddoppia ogni volta, poi sx e dx sono gli intervalli dove cerco il valore (che presumo siano il successivo di x fino alla fine nelle foglie del ST) e a e b alla fine non cambiano mai in b di sicuro va la fine in a ho messo 1, size, size+x+1 ma l’output risulta sempre errato.  
Di sicuro non mi trovo con qualcosa ma non riesco a capire cosa 😅

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [27 Giugno 2023, 8:27pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/4 "2023-06-27T20:27:17Z")

</div>

Ciao, per come è stato definito il segment tree gli intervalli per determinare la posizione del successivo di data[x] sono rispettivamente [0,size-1] e [x,size-1], chiaramente se non trova alcuna posizione restituisce -1.

---

<div class="post-metadata">

**Author:** ![AAALE](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/e0b2c6/32.png) [@AAALE](https://forum.olinfo.it/u/AAALE)\
**Post date:** [28 Giugno 2023, 5:54am UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/5 "2023-06-28T05:54:53Z")

</div>

La funzione chiedi dovrebbe restituire due numeri, uno più piccolo di _x_ e uno più grande

```auto
pair<int, int> chiedi(int x)

```

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [1 Luglio 2023, 2:21pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/6 "2023-07-01T14:21:08Z")

</div>

Ciao, ti ringrazio per l’aiuto perché ora sembra che ora la parte di destra è sistemata; sto provando a sistemare la parte a sinistra con qualche modifica alla get\_first (cambiando solo gli estremi di ricerca mi da sempre il risultato più a sinistra invece di quello più vicino a x) e ho modificato m in modo che si sposti a sinistra cosi

```auto
    int m = dx - (dx-sx)/2;

```

(ovviamente ho anche cambiato il nome della funzione per la ricorsione) ma mi va in errore e il sanitizer mi dice heap-buffer-overflow.  
Come sei riuscito a sistemare il bastione precedente?

```auto
#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
void build(int u, int sx, int dx, vector<int> data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
    ::size = 1;
    
    while(::size < N)
        ::size *= 2;
    nodes.assign(2*::size, -1); // totale nodi=2*N-1
    build(1, 0, ::size, data);
}
void cambia(int x, int h){
    int p = ::size + x; //size è il primo del vector
    nodes[p] = h;
    while(p>1){
        p/=2; //risalgo
        nodes[p] = max(nodes[2*p], nodes[2*p+1]);
    }
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = dx - (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = dx - (dx-sx)/2;
    int rs = prec(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return prec(2*pos+1, m+1, dx, a, b, x);
}

pair<int, int> chiedi(int x){
    int pos = succ(1, 0, ::size-1, x, ::size-1, nodes[x+::size]);
    int pos_ = prec(1, 0, ::size-1, 0, x, nodes[x+::size]);
    pair<int, int> a = make_pair(pos_, pos);
    return a;
}

```

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [1 Luglio 2023, 2:42pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/7 "2023-07-01T14:42:08Z")

</div>

Ciao, quello che devi cambiare nella funzione prec() rispetto alla succ() non è il modo di calcolare m, esso rimane invariato, si tratta semplicemente del valore medio tra [sx,dx]:

m = (sx+dx)/2

Quello che, invece, devi modificare nella funzione per trovare il precedente sono i nodi del segment tree, quelli di sinistra 2_i al posto di quelli di destra 2_+1, per il modo i cui sono distribuiti i nodi all’interno dell’albero.

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [1 Luglio 2023, 3:11pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/8 "2023-07-01T15:11:31Z")

</div>

Susami ma non sono familiare con i segment tree, devo modificare sx e dx così?

```auto
int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                sx = m; 
            }
            else{
                pos = 2*pos+1;
                dx = m+1;
            }
        }
        return sx;
    }
    int m = (dx-sx)/2;
    int rs = prec(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return prec(2*pos+1, m+1, dx, a, b, x);
}

```

cosi continua a darmi errore non so come muovermi, grazie per tutto il supporto

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [1 Luglio 2023, 3:23pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/9 "2023-07-01T15:23:39Z")

</div>

Attenzione:  
m = (sx + dx)/2;

oppure anche:  
m = sx + (dx - sx)/2;

Quello che non hai fatto, invece, è di invertire i nodi, questo si è importante.

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [1 Luglio 2023, 3:31pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/10 "2023-07-01T15:31:47Z")

</div>

Non mi è chiaro cosa significa invertire i nodi, devo rifare la funzione inizializza sul vettore iniziale invertito e usare la get\_first sul nuovo segment tree? Non impiegherebbe troppo tempo?  
Se vuoi puoi inviarmi qualche snippet di codice così cerco di capire meglio

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [1 Luglio 2023, 3:55pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/11 "2023-07-01T15:55:24Z")

</div>

No il segment tree è sempre lo stesso è solo la funzione prec() che deve essere implementata, non essendo forse abbastanza chiaro con “invertire i nodi da pari a dispari e viceversa”, devi in pratica sostituire, ad esempio:

```auto
if(nodes[2*pos+1] > x) { 
...
}
else {
...
 }

```

invece di:

```auto
if(nodes[2*pos] > x) { }

```

chiaramente tra parentesi devi mettere i valori giusti.  
Lo stesso devi fare poi nelle altre righe della funzione.

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [1 Luglio 2023, 7:51pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/12 "2023-07-01T19:51:30Z")

</div>

```auto
int prec(int pos, int sx, int dx, int a, int b, int x){
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos+1] > x){ 
                pos = 2*pos+1;
                sx = m+1; 
            }
            else{
                pos = 2*pos;
                dx = m;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int ls = prec(2*pos+1, m+1, dx, a, b, x);
    if(ls != -1) return ls;
    return prec(2*pos, sx, m, a, b, x);
}

```

Ho invertito la condizione come hai detto e ho sistemato le altre variabili ma continua ad andare in segmentation fault, penso di aver dato a sx e dx ogni valore possibile ma continua a non funzionare 😅

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [1 Luglio 2023, 10:10pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/13 "2023-07-01T22:10:15Z")

</div>

Il vector data deve essere passato alla funzione per reference per questo motivo va in TLE.  
Poi attenzione che le 2 funzioni prec() e succ() ti restituiscono -1 se non trovano gli estremi sx e dx al posto di 0 e N-1.  
Fatti questi aggiustamenti prendi 100/100.

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [2 Luglio 2023, 9:40am UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/14 "2023-07-02T09:40:05Z")

</div>

Ora rientro nel tempo e sono anche riuscito a risolvere il segmentation fault ma gli output sono tutti incorretti tranne il secondo caso di esempio, già ad esempio facendo Q 4 nel primo caso d’esempio mi viene calcolato 0 8 al posto di 2 7  
Ecco il codice aggiornato

```auto
#include<bits/stdc++.h>
using namespace std;
vector<int> nodes;
int size;
int N;
void build(int u, int sx, int dx, vector<int> &data){

    if(dx - sx == 1){
        if(sx < data.size())
            nodes[u] = data[sx];
    }
    else{
        int m = (sx+dx)/2;
        build(2*u, sx, m, data);
        build(2*u+1, m, dx, data);
        nodes[u]= max(nodes[2*u], nodes[2*u+1]);
    }
}
void inizializza(int N, vector<int> data){
    ::size = 1;
    
    while(::size < N)
        ::size *= 2;
    nodes.assign(2*::size, -1); // totale nodi=2*N-1
    build(1, 0, ::size, data);
}
void cambia(int x, int h){
    int p = ::size + x; //size è il primo del vector
    nodes[p] = h;
    while(p>1){
        p/=2; //risalgo
        nodes[p] = max(nodes[2*p], nodes[2*p+1]);
    }
}
int succ(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos] > x){ 
                pos = 2*pos;
                dx = m; 
            }
            else{
                pos = 2*pos+1;
                sx = m+1;
            }
        }
        return sx;
    }
    int m = sx + (dx-sx)/2;
    int rs = succ(2*pos, sx, m, a, b, x);
    if(rs != -1) return rs;
    return succ(2*pos+1, m+1, dx, a, b, x);
}
int prec(int pos, int sx, int dx, int a, int b, int x){ // a, b estremi
    if(sx > b or dx < a) return -1;
    if(a <= sx and dx <= b){
        if(nodes[pos] <= x) return -1;
        while(sx != dx){
            int m = sx + (dx-sx)/2;
            if(nodes[2*pos+1] > x){ 
                pos = 2*pos+1;
                sx = m+1; 
            }
            else{
                pos = 2*pos;
                dx = m;
            }
        }
        return dx;
    }
    int m = sx + (dx-sx)/2;
    int ls = prec(2*pos+1, sx, m, a, b, x);
    if(ls != -1) return ls;
    return prec(2*pos, m+1, dx, a, b, x);
}

pair<int, int> chiedi(int x){
    int pos = succ(1, 0, ::size-1, x, ::size-1, nodes[x+::size]);
    if(pos==-1) pos=N-1;
    int pos_ = prec(1, 0, ::size-1, 0, x, nodes[x+::size]);
    if (pos_==-1) pos_=0;
    pair<int, int> a = make_pair(pos_, pos);
    return a;
}

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [2 Luglio 2023, 10:22am UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/15 "2023-07-02T10:22:29Z")

</div>

Se sbagli un caso d’esempio, hai qualcosa di immediato su cui debuggare. Traccia l’esecuzione del tuo programma (usando un debugger, o anche solo mettendo cout nei punti importanti) e controlla che tutto sia come te lo aspetti. Quando trovi qualcosa che non va cerca di capire cosa causa il problema e mettilo a posto.  
Saper debuggare è estremamente importante, poiché implementare soluzioni funzionanti è parte di ciò che viene richiesto alle OII.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [2 Luglio 2023, 11:48am UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/16 "2023-07-02T11:48:06Z")

</div>

La version corretta della funzione prec() era quella pubblicata prima di quest’ultima versione ed è con quella che fa 100/100. L’unico errore che ti rimane da risolvere è quello di stampare N-1 al posto di -1.

---

<div class="post-metadata">

**Author:** ![FraMastro](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/f/48db29/32.png) [@FraMastro](https://forum.olinfo.it/u/FraMastro)\
**Post date:** [2 Luglio 2023, 3:10pm UTC](https://forum.olinfo.it/t/muraglia-st-help/8350/17 "2023-07-02T15:10:14Z")

</div>

100/100 Grazie ❤

Per stampare N-1 nella funzione inizializza che usa N ho preso il valore di N e lo ho assegnato a una variabile globale M nella mia soluzione per poi richiamarla con ::M nella funzione chiedi()