#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct dt{
int ma=1000000000;
int mi=0;
};
vector<dt> st;
void psh(int v,int tl, int tr,int tm){
st[v*2].mi=max(st[v*2].mi,st[v].mi);
st[v*2].ma=min(st[v*2].ma,st[v].ma);
st[v*2+1].mi=max(st[v*2+1].mi,st[v].mi);
st[v*2+1].ma=min(st[v*2+1].ma,st[v].ma);
st[v].mi=0;
st[v].ma=1000000000;
}
void query(int v, int tl, int tr,int l, int r, int x, int h){
if(l>r)return;
if(l==tl and r==tr){
if(x==1){
st[v].mi=max(st[v].mi,h);
st[v].ma=max(st[v].ma,h);
}
else{
st[v].mi=min(st[v].mi,h);
st[v].ma=min(st[v].ma,h);
}
}
else{
int tm=(tl+tr)/2;
psh(v,tl,tr,tm);
query(v*2,tl,tm,l,min(r,tm),x,h);
query(v*2+1,tm+1,tr,max(l,tm+1),r,x,h);
}
}
int get(int v, int tl, int tr, int pos){
if(tl==tr){
return st[v].mi;
}
int tm=(tl+tr)/2;
psh(v,tl,tr,tm);
if(pos<=tm)return get(v*2,tl,tm,pos);
else return get(v*2+1,tm+1,tr,pos);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
st.resize(2*n);
for(int i=0;i<k;i++){
query(1,0,n-1,left[i],right[i],op[i],height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=get(1,0,n-1,i);
}
}
