#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2000005
#define INF (int)1e9+5
int st[4*MAXN],lazy_lower[4*MAXN],lazy_upper[4*MAXN];//minimum segment tree
int final[MAXN];
int N;
void update(int from,int to,int low,int up,int v=1,int start=0,int end=N-1){
if(start==from&&end==to){
st[v]=max(st[v],low);
st[v]=min(st[v],up);
if(low>lazy_upper[v]){
lazy_upper[v]=lazy_lower[v]=low;
}else if(up<lazy_lower[v]){
lazy_lower[v]=lazy_upper[v]=up;
}else{
lazy_lower[v]=max(lazy_lower[v],low);
lazy_upper[v]=min(lazy_upper[v],up);
}
return;
}
int mid=(start+end)/2;
//propagate
update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
lazy_lower[v]=0;
lazy_upper[v]=INF;
if(to<=mid){
update(from,to,low,up,2*v,start,mid);
}else if(from>mid){
update(from,to,low,up,2*v+1,mid+1,end);
}else{
update(from,mid,low,up,2*v,start,mid);
update(mid+1,to,low,up,2*v+1,mid+1,end);
}
st[v]=min(st[2*v],st[2*v+1]);
}
void build(int v=1,int start=0,int end=N-1){
if(start==end){
lazy_upper[v]=INF;
return;
}
int mid=(start+end)/2;
build(2*v,start,mid);
build(2*v+1,mid+1,end);
lazy_upper[v]=INF;
}
void build_result(int v=1,int start=0,int end=N-1){
if(start==end){
final[start]=st[v];
return;
}
int mid=(start+end)/2;
//propagate
update(start,mid,lazy_lower[v],lazy_upper[v],2*v,start,mid);
update(mid+1,end,lazy_lower[v],lazy_upper[v],2*v+1,mid+1,end);
lazy_lower[v]=0;
lazy_upper[v]=INF;
build_result(2*v,start,mid);
build_result(2*v+1,mid+1,end);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
N=n;
build();
for(int i=0;i<k;i++){
if(op[i]==1){
update(left[i],right[i],height[i],INF);
}else{
update(left[i],right[i],0,height[i]);
}
}
build_result();
for(int i=0;i<n;i++){
finalHeight[i]=final[i];
}
return;
}
