Sto cercando di risolvere muraglia da un paio di giorni ma non sto avendo molto successo.
Credo di essere riuscito a comprendere il funzionamento della creazione di un segment tree e anche dell’update, però ancora non sono riuscito a comprendere come trovare il primo valore >x in uno specifico range.
//GRADER IGNORARE-------------------------------------------------------------
#include <utility>
#include <iostream>
#include <vector>
using namespace std;
// Declaring variables
static int R;
static vector<int> risultato1;
static vector<int> risultato2;
// Declaring functions
void inizializza(int N, vector<int> H);
// Functions ad-hoc for this grader
pair<int, int> chiedi(int x);
void cambia(int x, int h);
void leggi_eventi(int M) {
for (int i = 0; i < M; i++) {
char tipo;
cin >> tipo;
if (tipo == 'Q') {
int x;
cin >> x;
pair<int, int> risultato = chiedi(x);
risultato1[R] = risultato.first;
risultato2[R] = risultato.second;
R++;
} else {
int x, h;
cin >> x >> h;
cambia(x, h);
}
}
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// Reading input
int N, M;
cin >> N >> M;
vector<int> H(N);
risultato1.resize(M);
risultato2.resize(M);
for (int i = 0; i < N; i++) {
cin >> H[i];
}
// Calling functions
inizializza(N, H);
leggi_eventi(M);
// Writing output
for (int i = 0; i < R; i++) {
cout << risultato1[i] << ' ' << risultato2[i] << '\n';
}
return 0;
}
//RISOLUZIONE----------------------------------------------------------------------------------------------------------------
//SEGMENT TREE
vector<int> seg;
vector<int> torre;
int sizeN;
long long int build(int i, int l, int r, vector<int> &torri) {
if(r-l==1) return seg[i] = torri[l]; //caso base
int mid = (l+r)/2; //divido a metà
//creo i figli, e ricorsivamente risalgo al padre facendo sempre salire il maggiore.
seg[i] = max(build(2*i, l, mid, torri), build((2*i)+1, mid, r, torri));
//restituisco il valore del segmento
return seg[i];
}
void update(int i, int l, int r, int pos, long long int val) {
if(r-l==1) { seg[i] = val; return; } //caso base
int mid = (l+r)/2; //trova il centro
if(pos<mid) update(2*i, l, mid, pos, val); //metà sinistra
else update(2*i+1, mid, r, pos, val); //metà destra
seg[i] = max(seg[2*i],seg[2*i+1]); //aggiorno il valore con il massimo tra i due figli
}
int query_destra (int i, int l, int r, int ql, int qr, int x) {
//casi base
if (ql >= r or qr <= l) return -1;//nessuna intersezione
if (l >= ql and r <= qr) { //incluso
if(seg[i] <= x) return -1; //nel caso in cui il nodo è minore di X non è interessante
//return i; <--------------- probabilmente l'errore
}
int mid = (l + r) / 2;
printf("controllo valore:%d nodo:%d x:%d\n", seg[i], i, x);
//si da la priorità al primo valore, in caso non è un valore interessante, si scende al secondo
int ans = query_destra(2*i, l, mid, ql, qr, x);
if(ans != -1) return ans;
return query_destra(2*i+1, mid, r, ql, qr, x);
}
pair<int, int> chiedi(int x) {
//stampa il vettore
for(int i=0; i<sizeN*4; i++) printf("%d ", seg[i]); printf("\n");
return make_pair(0/*query_sinistra(1,0,sizeN, 0, x, torre[x])*/,query_destra(1, 0, sizeN, x, sizeN, torre[x]));
}
void cambia(int x, int h) {
update(1, 0, sizeN, x, h);
}
void inizializza(int N, vector<int> H) {
sizeN = H.size();
torre.resize(sizeN);
seg.resize(sizeN*4);
for(int i=0; i<sizeN; i++) torre[i] = H[i];
build(1,0,N,H);
}
Riesco a capire che mi manca il modo di far restituire i nella ricorsione (visto che al momento può solo restituire -1) ma non capisco la ragione per cui mettere return i; dopo i casi base non possa funzionare.
Qualsiasi tipo di aiuto è apprezzato, ringrazio in anticipo.