#include <iostream>
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
struct arbore {
bool flag;
int mini,maxi;
int l_mi,l_mx;
};
vector<arbore>aint;
///tip : 1=scad 2 cresc
void update(int nod,int st,int dr,int l,int r,int tip,int v) {
if(l <= st && dr <= r) {
///cazuri
if(tip == 1) {
aint[nod] = {true,min(aint[nod].mini,v),min(aint[nod].maxi,v),min(aint[nod].l_mx,v),min(aint[nod].l_mi,v)};
}
if(tip == 2) {
aint[nod] = {true,max(aint[nod].mini,v),max(aint[nod].maxi,v),max(aint[nod].l_mx,v),max(aint[nod].l_mi,v)};
}
return;
}
///push
if(aint[nod].flag) {
aint[2*nod] = {true,max(aint[nod].l_mi,aint[2*nod].mini),min(aint[nod].l_mx,aint[2*nod].maxi),max(aint[nod].l_mi,aint[2*nod].l_mi),min(aint[nod].l_mx,aint[2*nod].l_mx)};
aint[2*nod + 1] = {true,max(aint[nod].l_mi,aint[2*nod + 1].mini),min(aint[nod].l_mx,aint[2*nod + 1].maxi),max(aint[nod].l_mi,aint[2*nod + 1].l_mi),min(aint[nod].l_mx,aint[2*nod + 1].l_mx)};
aint[nod].flag = false;
aint[nod].l_mi = 0;
aint[nod].l_mx = 1e9;
}
int md = (st+dr)/2;
if(l <= md)
update(2*nod,st,md,l,r,tip,v);
if(r > md)
update(2*nod + 1,md+1,dr,l,r,tip,v);
aint[nod] = {false,max(aint[2*nod].mini,aint[2*nod + 1].mini),min(aint[2*nod].maxi,aint[2*nod + 1].maxi),0,(int)(1e9)};
}
int qeu(int nod,int st,int dr,int poz) {
if(aint[nod].flag) {
aint[2*nod] = {true,max(aint[nod].l_mi,aint[2*nod].mini),min(aint[nod].l_mx,aint[2*nod].maxi),max(aint[nod].l_mi,aint[2*nod].l_mi),min(aint[nod].l_mx,aint[2*nod].l_mx)};
aint[2*nod + 1] = {true,max(aint[nod].l_mi,aint[2*nod + 1].mini),min(aint[nod].l_mx,aint[2*nod + 1].maxi),max(aint[nod].l_mi,aint[2*nod + 1].l_mi),min(aint[nod].l_mx,aint[2*nod + 1].l_mx)};
aint[nod].flag = false;
aint[nod].l_mi = 0;
aint[nod].l_mx = 1e9;
}
if(st==dr)
return aint[nod].mini;
int md = (st+dr)/2;
if(poz <= md)
return qeu(2*nod,st,md,poz);
else
return qeu(2*nod + 1,md+1,dr,poz);
}
void buildWall(int n, int k,
int op[], int left[], int right[],
int height[], int finalHeight[]) {
const int INF = 1000000000;
aint.assign(4*n, {false, 0, 0, 0, INF});
for (int i = 0; i < k; i++) {
int tip = (op[i] == 1 ? 2 : 1);
update(1, 0, n-1, left[i], right[i], tip, height[i]);
}
for (int j = 0; j < n; j++) {
finalHeight[j] = qeu(1, 0, n-1, j);
}
}
