#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
/*struct Nodo{
int A_adir, Remover;
};*/
vector<int> _rbol, Propagable, a;
bool Cambio = 1;
//vector<Nodo> Propagable;
//Nodo Nada;
/*void Propagar(int p){
if(Propagable[p].A_adir == -22 and Propagable[p].Remover != -22){
_rbol[p] = min(Propagable[p].Remover, _rbol[p]);
if(p * 2 < _rbol.size()){
if(Propagable[p * 2].A_adir == -22 and Propagable[p * 2].Remover == -22) Propagable[p * 2].Remover = Propagable[p].Remover;
else if(Propagable[p * 2].A_adir == -22) Propagable[p * 2].Remover = min(Propagable[p * 2].Remover, Propagable[p].Remover);
else if(Propagable[p * 2].Remover == -22){
if(Propagable[p * 2].A_adir >)
}
}
} else if(Propagable[p].A_adir != -22 and Propagable[p].Remover == -22){
_rbol[p] = max(Propagable[p].Remover, _rbol[p]);
}
}
int Consulta(int i, int d, int p, int I){
Propagar(p);
if(i == I and d == I) return _rbol[p];
if(i > I or d < I) return -0;
int P = (i + d) / 2;
return Consulta(i, P, p * 2, I) + Consulta(P + 1, d, p * 2 + 1, I);
}
void Actualizar(int i, int d, int p, int I, int D, int v, bool t){
Propagar(p);
if(i >= I and d <= D){
if(t == 0) Propagable[p].A_adir = v;
else Propagable[p].Remover = v;
Propagar(p);
return;
}
if(i > D or d < I) return;
int P = (i + d) / 2;
Actualizar(i, P, p * 2, I, D, v, t);
Actualizar(P + 1, d, p * 2 + 1, I, D, v, t);
}*/
void Propagar(int p){
if(Propagable[p] != -22){
//cerr<<p<<" "<<Propagable[p]<<" "<<_rbol[p]<<" "<<(int)Cambio<<"\n";
if(Cambio){
_rbol[p] = max(_rbol[p], Propagable[p]);
//cerr<<p<<" -> "<<_rbol[p]<<"\n";
if(p * 2 < _rbol.size()) Propagable[p * 2] = max(Propagable[p * 2], Propagable[p]);
if(p * 2 + 1 < _rbol.size()) Propagable[p * 2 + 1] = max(Propagable[p * 2 + 1], Propagable[p]);
} else {
_rbol[p] = min(_rbol[p], Propagable[p]);
//cerr<<p<<" -> "<<_rbol[p]<<"\n";
if(p * 2 < _rbol.size()){
if(Propagable[p * 2] == -22) Propagable[p * 2] = Propagable[p];
else Propagable[p * 2] = min(Propagable[p * 2], Propagable[p]);
}
if(p * 2 + 1 < _rbol.size()){
if(Propagable[p * 2 + 1] == -22) Propagable[p * 2 + 1] = Propagable[p];
else Propagable[p * 2 + 1] = min(Propagable[p * 2 + 1], Propagable[p]);
}
}
}
Propagable[p] = -22;
}
void Crear(int i, int d, int p){
if(i == d){
_rbol[p] = a[i];
return;
}
int P = (i + d) / 2;
Crear(i, P, p * 2);
Crear(P + 1, d, p * 2 + 1);
}
int Consulta(int i, int d, int p, int I){
Propagar(p);
//cerr<<i<<" "<<d<<" "<<p<<" "<<I<<" "<<_rbol[p]<<"\n";
if(i == I and d == I) return _rbol[p];
if(i > I or d < I) return -0;
int P = (i + d) / 2;
return Consulta(i, P, p * 2, I) + Consulta(P + 1, d, p * 2 + 1, I);
}
void Actualizar(int i, int d, int p, int I, int D, int v){
Propagar(p);
if(i >= I and d <= D){
Propagable[p] = v;
Propagar(p);
return;
}
if(i > D or d < I) return;
int P = (i + d) / 2;
Actualizar(i, P, p * 2, I, D, v);
Actualizar(P + 1, d, p * 2 + 1, I, D, v);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
_rbol.assign(n * 4 + 22, 0);
a.assign(n, 0);
/*Nada.A_adir = -22;
Nada.Remover = -22;
Propagable.assign(n * 4 + 22, Nada);*/
Propagable.assign(n * 4 + 22, -22);
Crear(0, n - 1, 1);
for(int i = 0; i < k; i++){
if(op[i] == 2 and Cambio){
for(int j = 0; j < n; j++){
a[j] = Consulta(0, n - 1, 1, j);
//cerr<<a[j]<<" ";
}
//cerr<<"\n";
Cambio = 0;
Crear(0, n - 1, 1);
Propagable.assign(n * 4 + 22, -22);
}
Actualizar(0, n - 1, 1, left[i], right[i], height[i]);
/*for(int j = 0; j < n; j++) cerr<<Consulta(0, n - 1, 1, j)<<" ";
cerr<<"\n";*/
/*for(int j = 0; j < n * 4 + 22; j++) cerr<<Propagable[j]<<" ";
cerr<<"\n";*/
}
for(int i = 0; i < n; i++){
finalHeight[i] = Consulta(0, n - 1, 1, i);
//cerr<<finalHeight[i]<<" ";
}
//cerr<<"\n";
return;
}
/*
4 6
1 0 3 5
1 0 1 3
1 2 3 7
2 0 1 8
2 1 3 6
2 0 2 1
*/
