Buongiorno a tutti.
Stavo risolvendo Muraglia (algobadge) e ho implementato un segment tree. Ho implementato con successo le funzioni inizializza() e cambia(), sono riuscito (credo) a implementare la funzione che trova il maggiore a sinistra di X ma non a destra di X. Il mio codice è il seguente:
#include <utility>
#include <vector>
#include<iostream>
using namespace std;
static int R;
static vector<int> risultato1;
static vector<int> risultato2;
//==================================== grader ========================================
#include<algorithm>
using namespace std;
vector<vector<int>> segTree;
int magSinistra(int x, int i, int h, int &topG){
int temp;
if(x<=0||i>segTree.size()){
return 0;
}
if(segTree[i][x]==h){
temp=magSinistra(x/2, i+1, segTree[i][x], topG);
}else{
topG=segTree[i][x];
return x*2;
}
/*if(x%2==0){
if(temp==x){
return x;
}else if(temp==x+1){
return x+1;
}
}*/
if(temp==0){
return 0;
}
if(segTree[i][temp]==topG){
return temp*2;
}
return (temp+1)*2;
}
int magDestra(int x, int i, int h, int &topG){
int temp;
if(x>=segTree[i].size()-1||i>segTree.size()){
return segTree[i].size()-1;
}
if(segTree[i][x]==h){
temp=magSinistra(x/2, i+1, segTree[i][x], topG);
}
if(temp==segTree[i].size()-1){
return (segTree[i].size()-1)*2;
}
if(segTree[i][temp]==topG){
return temp*2;
}
return (temp+1)*2;
}
pair<int, int> chiedi(int x) {
int temp;
if(x%2==0){
return {magSinistra(x-1,0, segTree[0][x-1], temp)/2,magDestra(x,0, segTree[0][x], temp)/2};
}
return {magSinistra(x,0, segTree[0][x], temp)/2,magDestra(x+1,0, segTree[0][x+1], temp)/2};
}
void update(int x, int i, int h){ //fatto (ottimizzabile)
if(i==segTree.size()){
return;
}
segTree[i][x]=h;
if(x%2==0){
update(x/2, i+1, max(h, segTree[i][x+1]));
}else{
update(x/2, i+1, max(h, segTree[i][x-1]));
}
}
void cambia(int x, int h) {
update(x,0,h);
//segTree[0][x]=h;
}
void stampa(vector<vector<int>> a){
for(int i=0; i<a.size(); i++){
for(int j=0; j<a[i].size(); j++){
cout<<a[i][j]<<" ";
}
cout<<"\n";
}
}
void setup(int N, vector<int> H){
if(N==1){
return;
}
bool sus=false;
if(N%2!=0){
H.resize(N+1);
H[N]=0;
N++;
sus=true;
}
vector<int> temp;
for(int i=0; i<N; i+=2){
temp.push_back(max(H[i], H[i+1]));
}
if(sus){
temp.resize(N-1);
}
segTree.push_back(temp);
setup(N/2, temp);
}
void inizializza(int N, vector<int> H) { //fatto
segTree.push_back(H);
setup(N,H);
}
//==================================== grader ========================================
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);
stampa(segTree);
cout<<"\n";
}
}
}
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);
//stampa(segTree);
leggi_eventi(M);
// Writing output
for (int i = 0; i < R; i++) {
cout << risultato1[i] << ' ' << risultato2[i] << '\n';
}
return 0;
}
Qualcuno potrebbe indicarmi eventuali errori e se il mio ragionamento ha senso?
Grazie in anticipo.