#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
struct SegmentTree{
int n;
vector<pair<int, int>> t;
void init(int _n){
n=_n;
t.assign(4*n+1, {-inf, inf});
}
void build(int k, int l, int r){
if (l==r){
t[k]={0, 0};
return;
}
int mid=(l+r)>>1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
}
void apply(int k, pair<int, int> val){
if (t[k].second<val.first) t[k]={val.first, val.first};
else if (t[k].first>val.second) t[k]={val.second, val.second};
else t[k]={max(t[k].first, val.first), min(t[k].second, val.second)};
}
void push(int k){
if (t[k]!=pair<int, int>{-inf, inf}){
apply(k<<1, t[k]);
apply(k<<1|1, t[k]);
t[k]={-inf, inf};
}
}
void update(int k, int l, int r, int L, int R, pair<int, int> val){
if (r<L || R<l) return;
if (L<=l && r<=R){
apply(k, val);
return;
}
push(k);
int mid=(l+r)>>1;
update(k<<1, l, mid, L, R, val);
update(k<<1|1, mid+1, r, L, R, val);
}
void get_all(int k, int l, int r, int ans[]){
if (l==r){
ans[l]=t[k].first;
return;
}
push(k);
int mid=(l+r)>>1;
get_all(k<<1, l, mid, ans);
get_all(k<<1|1, mid+1, r, ans);
}
} st;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
st.init(n);
st.build(1, 0, n-1);
for (int i=0; i<k; ++i){
int l=left[i], r=right[i], h=height[i];
int lg=__lg(r-l+1);
if (op[i]==1){
st.update(1, 0, n-1, l, r, {h, inf});
}else{
st.update(1, 0, n-1, l, r, {-inf, h});
}
}
st.get_all(1, 0, n-1, finalHeight);
return;
}
