Muraglia, non va la query

Aiuto
1

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.

#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]);



}
2

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

4

ho provato a cambiare il costruttore in:

 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

5

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 per la comprensione dei segment.

1 Mi Piace
6

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

#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);
        }
    }
}
7

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.

#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]);







}
8

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

9

ho cambiato update in

 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

10

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

11

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