# Muraglia, non va la query

**URL:** <https://forum.olinfo.it/t/muraglia-non-va-la-query/8626>\
**Category:** Aiuto\
**Created:** [27 Novembre 2023, 1:21am UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626 "2023-11-27T01:21:44Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 1:21am UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/1 "2023-11-27T01:21:44Z")

</div>

sto provando a risolvere muraglia con un segment tree e sembra funzionare tutto tranne la query, se riesco a risolvere quella per guardare a destra sono abbastanza sicuro di riuscire a fare facilmente anche quella verso sinistra ma non riesco a capire perchè non funziona ora.

```auto
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("input.txt");
ofstream fout ("output.txt");

struct segmentTree {
    int N;
    vector<long long>st;

    long long build(int i,int L, int R, vector<long long> &A)
    {
        if(R - L == 1)
        {
            return st[i]=A[L];
        }

        int mid= (L+R)/2;
        st[i]= max(build(i*2,L,mid,A),
                   build(i*2+1,mid,R,A));
        return st[i];

    }

    segmentTree (vector<long long> &A)
    {
        N=A.size();
        st.resize(N*4);
        build(1,0,N,A);
    }

    void update (int i, int L, int R, int pos, long long val)
    {
        if(R-L == 1)
        {
            st[i]=val;
            return;
        }
        int mid= (R+L)/2;
        if(pos<mid)
        {
            update(2*i,L,mid,pos,val);
        }else{
            update(2*i+1,L,mid,pos,val);
        }
        st[i]=max(st[2*i],st[2*i+1]);
    }

    void update(int pos,long long val)
    {
        update(1,0,N,pos,val);
    }

    int guardaADestra(int i,int tl,int tr,int l,int r,int val)
    {
        //se non è possibile trovare un caso utile return -1
        if(tl>r || tr<l)return -1;
        if(st[i]<=val)return -1;

        if(tl==tr)return tl;

        int tm= tl + (tr-tl)/2;
        int L=guardaADestra(2*i,tl,tm,l,r,val);
        if(L!=-1)return L;
        int R=guardaADestra(2*i+1,tm+1,tr,l,r,val);
        return R;

    }

    int guardaADestra(int pos,int val)
    {
        return guardaADestra(1,0,N-1,pos+1,N,val);//non sono sicuro dei valori, ho provato a cambiarli ma non cambia il risultato
    }

};

int main()
{
    //primo testcase
    int N=14;
    vector<long long>A(N);
    for(int i=0;i<14;i++)fin>>A[i];

    segmentTree st(A);

    cout<<st.guardaADestra(4,A[4]);

}

```

---

<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 Novembre 2023, 5:46pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/2 "2023-11-27T17:46:42Z")

</div>

Per operare correttamente il tuo segment tree deve avere una lunghezza pari a 2\*Size con Size = 2^k \>= N.

---

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 6:15pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/4 "2023-11-27T18:15:09Z")

</div>

ho provato a cambiare il costruttore in:

```auto
 segmentTree (vector<long long> &A)
    {
        N=A.size();
        st.resize(N*2);
        build(1,0,N,A);
    }

```

con N \* 2 invece che N \* 4 ma non cambia

---

<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 Novembre 2023, 6:39pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/5 "2023-11-27T18:39:25Z")

</div>

Ma N non è una potenze di 2^k \>= N!  
Nell’esempio con N = 14, nel costruttore deve venire N = 2^4 = 16.  
La tua query non funziona correttamente perché sia il metodo build(1, 0, N) e sia update(1. 0, N) usano l’intervallo aperto [1, N) mentre il metodo query(1, 0, N-1) usa l’intervallo chiuso [0, N-1]. In pratica devi usare per tutti i metodi lo stesso tipo di intervallo.  
Ti consiglio anche questa [ottima guida](https://forum.olinfo.it/t/introduzione-ai-segment-tree/8481) per la comprensione dei segment.

---

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 7:30pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/6 "2023-11-27T19:30:09Z")

</div>

ho modificato la funzione guarda a destra e sembrava funzionare ma dopo aver fatto il main e le altre funzioni mi stampa sempre -1

```auto
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("input.txt");
ofstream fout ("output.txt");

    int N;
    vector<long long>st;
    vector <long long>A;

    long long build(int i,int L, int R, vector<long long> &A)
    {
        if(R - L == 1)
        {
            return st[i]=A[L];
        }

        int mid= (L+R)/2;
        st[i]= max(build(i*2,L,mid,A),
                   build(i*2+1,mid,R,A));
        return st[i];

    }

    void update (int i, int L, int R, int pos, long long val)
    {
        if(R-L == 1)
        {
            st[i]=val;
            return;
        }
        int mid= (R+L)/2;
        if(pos<mid)
        {
            update(2*i,L,mid,pos,val);
        }else{
            update(2*i+1,L,mid,pos,val);
        }
        st[i]=max(st[2*i],st[2*i+1]);
    }

    void update(int pos,long long val)
    {
        update(1,0,N,pos,val);
    }

    int guardaADestra(int i,int tl,int tr,int l,int r,int val)
    {
        //se non è possibile trovare un caso utile return -1
        if(tl>r || tr<l)return -1;
        if(st[i]<=val)return -1;

        if(tr-tl==1)return tl;

        int tm= tl + (tr-tl)/2;
        int L=guardaADestra(2*i,tl,tm,l,r,val);
        if(L!=-1)return L;
        int R=guardaADestra(2*i+1,tm,tr,l,r,val);
        return R;

    }

    int guardaADestra(int pos,int val)
    {
        return guardaADestra(1,0,N,pos,N,val);//non sono sicuro dei valori, ho provato a cambiarli ma non cambia il risultato
    }

        int guardaASinistra(int i,int tl,int tr,int l,int r,int val)
    {
        //se non è possibile trovare un caso utile return -1
        if(tl>r || tr<l)return -1;
        if(st[i]<=val)return -1;

        if(tr-tl==1)return tr;

        int tm= tl + (tr-tl)/2;
        int R=guardaASinistra(2*i+1,tm,tr,l,r,val);

        if(R!=-1)return R;
        int L=guardaASinistra(2*i,tl,tm,l,r,val);

        return L;

    }

    int guardaASinistra(int pos,int val)
    {
        return guardaASinistra(1,0,N,N,pos+1,val);//non sono sicuro dei valori, ho provato a cambiarli ma non cambia il risultato
    }

void inizializza(int N, vector<int> H)
{
    A.resize(N);
    for(int i=0;i<N;i++)A[i]=H[i];
    st.resize(N*4);
    build(1,0,N,A);
}

void cambia(int x, int h)
{
    update(x,h);
}

pair<int, int> chiedi(int x)
{
    int d=guardaADestra(x,A[x]);
    int s=guardaASinistra(x,A[x]);
    return make_pair(s,d);
}

int main()
{
    int N,q;
    fin>>N>>q;
    vector<int>H(N);
    for (int i=0;i<N;i++)fin>>H[i];
    inizializza(N,H);
    char mossa;
    int a,b;
    pair<int,int>sol;
    for(int i =0;i<q;i++)
    {
        fin>>mossa;
        if(mossa=='Q')
        {
            fin>>a;
           sol= chiedi(a);
           cout<<sol.first<<" "<<sol.second<<endl;
        }
        if(mossa=='S')
        {
            fin>>a>>b;
            cambia(a,b);
        }
    }
}

```

---

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 7:59pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/7 "2023-11-27T19:59:11Z")

</div>

cambiando un p’ sono riuscito a farlo funzionare, ma col primo testcase nell’ultimo output non da i valori giusti, penso che forse anche la costruzione del st potrebbe essere sbagliata perchè mandandolo in output non sembra giusto.

```auto
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("input.txt");
ofstream fout ("output.txt");

    int N;
    vector<long long>st;
    vector<int>A;

    long long build(int i,int L, int R)
    {
        if(R - L == 1)
        {
            return st[i]=A[L];
        }

        int mid= (L+R)/2;
        st[i]= max(build(i*2,L,mid),
                   build(i*2+1,mid,R));
        return st[i];

    }

    void crea ()
    {
        N=A.size();
        st.resize(N*4);
        build(1,0,N);
    }

    void update (int i, int L, int R, int pos, long long val)
    {
        if(R-L == 1)
        {
            st[i]=val;
            return;
        }
        int mid= (R+L)/2;
        if(pos<mid)
        {
            update(2*i,L,mid,pos,val);
        }else{
            update(2*i+1,mid,R,pos,val);
        }
        st[i]=max(st[2*i],st[2*i+1]);
    }

    void update(int pos,long long val)
    {
        update(1,0,N,pos,val);
    }

    int guardaADestra(int i,int tl,int tr,int l,int r,int val)
    {
        //se non è possibile trovare un caso utile return -1
        if(tl>r || tr<l)return -1;
        if(st[i]<=val)return -1;

        if(tr-tl==1)return tl;

        int tm= tl + (tr-tl)/2;
        int L=guardaADestra(2*i,tl,tm,l,r,val);
        if(L!=-1)return L;
        int R=guardaADestra(2*i+1,tm,tr,l,r,val);
        return R;

    }

    int guardaADestra(int pos,int val)
    {
        return guardaADestra(1,0,N,pos,N,val);//non sono sicuro dei valori, ho provato a cambiarli ma non cambia il risultato
    }

     int guardaASinistra(int i,int tl,int tr,int l,int r,int val)
    {
        //se non è possibile trovare un caso utile return -1
        if(tl>r || tr<l)return -1;
        if(st[i]<=val)return -1;

        if(tr-tl==1)return tl;

        int tm= tl + (tr-tl)/2;
        int R=guardaASinistra(2*i+1,tm,tr,l,r,val);

        if(R!=-1)return R;
        int L=guardaASinistra(2*i,tl,tm,l,r,val);
        return L;

    }

    int guardaASinistra(int pos,int val)
    {
        return guardaASinistra(1,0,N,0,pos+1,val);//non sono sicuro dei valori, ho provato a cambiarli ma non cambia il risultato
    }

pair<int, int> chiedi(int x)
{
    int s = guardaASinistra(x,A[x]);
    int d=guardaADestra(x,A[x]);
    if(s==-1)s=0;
    if(d==-1)d=A.size()-1;
    return make_pair(s,d);

}

void inizializza(int N, vector<int> H)
{
    A.resize(N);
    for(int i=0;i<H.size();i++)A[i]=H[i];
    crea();
}

void cambia(int x, int h)
{
    update(x,h);
}

int main()
{
    //primo testcase
    int q;
    fin>>N>>q;
    A.resize(N);
    for(int i=0;i<14;i++)fin>>A[i];
    inizializza(N,A);
    pair<int,int>sol;
    int a,b;
    char mossa;

    for(int i=0;i<q;i++)
    {
        fin>>mossa;
        if(mossa=='Q')
        {
            fin>>a;
            sol=chiedi(a);
            cout<<sol.first<<" "<<sol.second<<endl;
        }else
        {
            fin>>a>>b;
            cambia(a,b);
        }
    }

    cout<<guardaASinistra(4,A[4]);

}

```

---

<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 Novembre 2023, 8:52pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/8 "2023-11-27T20:52:23Z")

</div>

Non devi aggiornare solo il segment tree nelle query di tipo Q ma anche l’altezza dei bastioni.

---

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 8:59pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/9 "2023-11-27T20:59:09Z")

</div>

ho cambiato update in

```auto
 void update(int pos,long long val)
    {
        update(1,0,N,pos,val);
        A[pos]=val;
    }

```

aggiungendo A[pos]=val per cambiare l’altezza dei bastioni e ora il primo testcase funziona, ma nessunaltro funziona

---

<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 Novembre 2023, 9:14pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/10 "2023-11-27T21:14:36Z")

</div>

Nelle query sinistra e destra l’intervallo non valido deve comprendere anche gli estremi.

---

<div class="post-metadata">

**Author:** ![LorenzoMorini](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/dec6dc/32.png) [@LorenzoMorini](https://forum.olinfo.it/u/LorenzoMorini)\
**Post date:** [27 Novembre 2023, 9:26pm UTC](https://forum.olinfo.it/t/muraglia-non-va-la-query/8626/11 "2023-11-27T21:26:25Z")

</div>

grazie mille ora funziona, scusa per il casino ma era un nuovo argomento per me e non lo avevo appreso pienamente