#include "wall.h"
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2000000;
pair<int,int> seg[4*N+7];
void push(int l,int r,int node){
if(l==r) return ;
int ll=node*2;
int rr=node*2+1;
seg[ll].first = min(seg[ll].first, seg[node].first);
seg[ll].first = max(seg[ll].first, seg[node].second);
seg[ll].second = min(seg[ll].second, seg[node].first);
seg[ll].second = max(seg[ll].second, seg[node].second);
seg[rr].first = min(seg[rr].first, seg[node].first);
seg[rr].first = max(seg[rr].first, seg[node].second);
seg[rr].second = min(seg[rr].second, seg[node].first);
seg[rr].second = max(seg[rr].second, seg[node].second);
}
void update(int l,int r,int idx1,int idx2,int val,int node,int mode){
push(l,r,node);
if(l>idx2 || r<idx1) return ;
if(l>=idx1 && r<=idx2){
if(mode){
seg[node].first=min(seg[node].first,val);
seg[node].second=min(seg[node].second,val);
}
else{
seg[node].first=max(seg[node].first,val);
seg[node].second=max(seg[node].second,val);
}
return ;
}
seg[node].first=1e9;
seg[node].second=-1e9;
int mid=(l+r)>>1;
update(l,mid,idx1,idx2,val,node*2,mode);
update(mid+1,r,idx1,idx2,val,node*2+1,mode);
}
void query(int l,int r,int node, int arr[]){
if(l==r){
arr[l-1]=seg[node].first;
return ;
}
push(l,r,node);
int mid=(l+r)>>1;
query(l,mid,node*2,arr);
query(mid+1,r,node*2+1,arr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; ++i) {
update(1,n,left[i]+1,right[i]+1,height[i],1,op[i]-1);
}
query(1,n,1,finalHeight);
return;
}
