Ciao a tutti. Stavo cercando di risolvere muraglia con un segment tree (ho visto gli altri thread, ma ho preferito fare la mia implementazione) e sono arrivato a questo codice. Nonostante questo, ho difficoltà con la funzione CHIEDI(). Non riesco ad elaborare una singola implementazione di questa che funzioni. Sono arrivato alla corrente. Allego tutto il codice in quanto non è molto standard come implementazione.
#include <utility>
#include <iostream>
#include <vector>
#include<fstream>
using namespace std;
// Declaring variables
static int R;
static vector<int> risultato1;
static vector<int> risultato2;
//====================== grader ==========================
#include<cmath>
#include <vector>
#include<iostream>
using namespace std;
struct treeValue {
int range_left;
int range_right;
int value;
treeValue* upper=NULL;
treeValue* left_child=NULL;
treeValue* right_child=NULL;
};
vector<vector<treeValue>> segmentTree;
void stampa(){ //used for temporary debugging and verifying that the pointer returned by secureAt() works
for(int i=0; i<segmentTree.size(); i++){
for(int j=0; j<segmentTree[i].size(); j++){
cout<<segmentTree[i][j].value<<"\t\t";
}
cout<<"\n";
for(int j=0; j<segmentTree[i].size(); j++){
cout<<&segmentTree[i][j]<<"\t";
}
cout<<"\n";
for(int j=0; j<segmentTree[i].size(); j++){
cout<<"["<<segmentTree[i][j].range_left<<":"<<segmentTree[i][j].range_right<<"]\t\t";
}
cout<<"\n";
for(int j=0; j<segmentTree[i].size(); j++){
cout<<segmentTree[i][j].left_child<<"\t";
}
cout<<"\n";
for(int j=0; j<segmentTree[i].size(); j++){
cout<<segmentTree[i][j].right_child<<"\t";
}
cout<<"\n";
for(int j=0; j<segmentTree[i].size(); j++){
cout<<segmentTree[i][j].upper<<"\t";
}
cout<<"\n\n";
}
cout<<"\n================================================\n\n"/*<<sizeof(treeValue)*/;
}
treeValue* secureAt(const int i, vector<treeValue>& a){
if(i<0){
return &a[0];
}else if(i>=a.size()){
return &a.back();
}
return &a[i];
}
void inizializza(int N, vector<int> H){ //works (tested)
segmentTree.resize((int)ceil(log2((float)N))+1);
int temp=N, k=0;
bool exit=false;
do{
segmentTree[k].resize(temp);
exit=temp==1;
k++;
temp=(int)ceil((float)temp/2);
}while(!exit);
for(int i=0; i<N; i++){
segmentTree[0][i].value=H[i];
segmentTree[0][i].range_left=i;
segmentTree[0][i].range_right=i;
}
int currentLayer=0;
while(segmentTree[currentLayer].size()!=1){
for(int i=0; i<segmentTree[currentLayer].size(); i+=2){
segmentTree[currentLayer+1][i/2].value=max(secureAt(i,segmentTree[currentLayer])->value, secureAt(i+1,segmentTree[currentLayer])->value);
segmentTree[currentLayer+1][i/2].range_left=secureAt(i, segmentTree[currentLayer])->range_left;
segmentTree[currentLayer+1][i/2].range_right=secureAt(i+1, segmentTree[currentLayer])->range_right;
segmentTree[currentLayer][i].upper=&segmentTree[currentLayer+1][i/2];
secureAt(i+1, segmentTree[currentLayer])->upper=&segmentTree[currentLayer+1][i/2];
segmentTree[currentLayer+1][i/2].left_child=secureAt(i, segmentTree[currentLayer]);
segmentTree[currentLayer+1][i/2].right_child=secureAt(i+1, segmentTree[currentLayer]);
}
currentLayer++;
}
//stampa();
}
int query_left(treeValue* currentValue, treeValue* queriedValue){
if(currentValue->range_left>=queriedValue->range_right){
return -1;
}
if(queriedValue->value>currentValue->value){
return -1;
}
if(currentValue->right_child==NULL){
return currentValue->range_left;
}
int temp=query_left(currentValue->right_child, queriedValue);
if(temp!=-1){return temp;}
temp=query_left(currentValue->left_child, queriedValue);
if(temp!=-1){return temp;}
return 0;
}
int query_right(treeValue* currentValue, treeValue* queriedValue){
if(currentValue->range_right<=queriedValue->range_left){
return -1;
}
if(currentValue->value<=queriedValue->value){
return -1;
}
if(currentValue->left_child==NULL){
return currentValue->range_left;
}
int temp=query_right(currentValue->left_child, queriedValue);
if(temp!=-1){return temp;}
temp=query_right(currentValue->right_child, queriedValue);
if(temp!=-1){return temp;}
return segmentTree[0].size()-1;
}
pair<int, int> chiedi(int x){ //(uses the pointer system to avoid confusion with indexes)
treeValue* queriedValue=&segmentTree[0][x];
treeValue* currentValue=&segmentTree.back().back(); //start from the root of the tree
return {query_left(currentValue, queriedValue), query_right(currentValue, queriedValue)};
}
void cambia(int x, int h){ //(uses the pointer system to avoid confusion with indexes)
int temp;
treeValue* currentValue=&segmentTree[0][x];
currentValue->value=h;
while(currentValue->upper!=NULL){
currentValue=currentValue->upper;
temp=max(currentValue->left_child->value,(*currentValue).right_child->value);
if(currentValue->value==temp){
break; //minor optimization: if the current value is the same as the maximum, stop updating, since the change value won't escalate anymore
}else{
currentValue->value=temp;
}
}
//stampa();
}
//====================== grader ==========================
// 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() {
// Reading input
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ofstream fout("output.txt");
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++) {
fout << risultato1[i] << ' ' << risultato2[i] << '\n';
}
fout.close();
return 0;
}
Perdonate se ho fatto un uso non ottimale dei puntatori, sono nuovo all’argomento 
Ringrazio in anticipo chiunque aiuti.