#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct lazyTag{
int chmin;
int chmax;
lazyTag(int a,int b){
chmin = a;
chmax = b;
}
void merge(lazyTag a){
chmin = max(min(chmin,a.chmin),a.chmax);
chmax = min(max(chmax,a.chmax),a.chmin);
}
};
struct lazySegmentTree{
vector<int> l;
vector<lazyTag> lazy;
int n = 1;
lazySegmentTree(vector<int> a){
while(n<a.size()){
n *= 2;
}
for(int i=0;i<n;i++){
lazy.push_back(lazyTag(123456789,0));
}
for(int i=0;i<n;i++){
if(i<a.size()){
lazy.push_back(lazyTag(a[i],a[i]));
}
else{
lazy.push_back(lazyTag(123456789,0));
}
}
}
void apply(int left,int right,int index,lazyTag tag){
lazy[index].merge(tag);
}
void push(int left,int right,int index){
int mid = (left+right)/2;
apply(left,mid,2*index,lazy[index]);
apply(mid,right,2*index+1,lazy[index]);
lazy[index] = lazyTag(123456789,0);
}
void update(int i,int j,lazyTag tag,int left=0,int right=-1,int index=1){
if(right==-1){
right = n;
}
if(i>=right||j<=left){
return;
}
if(i<=left&&j>=right){
apply(left,right,index,tag);
return;
}
push(left,right,index);
int mid = (left+right)/2;
update(i,j,tag,left,mid,2*index);
update(i,j,tag,mid,right,2*index+1);
}
void query(int left=0,int right=-1,int index=1){
if(right==-1){
right = n;
}
if(index<n){
push(left,right,index);
int mid = (left+right)/2;
query(left,mid,2*index);
query(mid,right,2*index+1);
}
}
vector<int> get(){
query();
vector<int> ans;
for(int i=0;i<n;i++){
ans.push_back(lazy[i+n].chmin);
}
return ans;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<int> a(n,0);
lazySegmentTree st(a);
for(int i=0;i<k;i++){
if(op[i]==1){
st.update(left[i],right[i]+1,lazyTag(123456789,height[i]));
}
else{
st.update(left[i],right[i]+1,lazyTag(height[i],0));
}
}
vector<int> ans = st.get();
for(int i=0;i<n;i++){
finalHeight[i] = ans[i];
}
return;
}
