#include "wall.h"
#include <bits/stdc++.h>
#define le node+node
#define ri node+node+1
#define mid (l+r)/2
#define ll long long
using namespace std;
const int inf = 2e6+9,MX = 1e9+9;
int opmin[inf<<2],opmax[inf<<2];
void build(int node,int l,int r){
opmin[node] = MX;
opmax[node] = 0;
if(l == r)
return;
build(le,l,mid);
build(ri,mid+1,r);
}
void tochild(int child,int node){
opmin[child] = min( opmin[child] , opmin[node] );//If you lower to height h on the child and to
//height h' on the parent after that, only min(h,h') will take effect
opmax[child] = max( opmax[child] , opmax[node] );//If you increase to height h on the child and then increase to
//height h' on the parent, only max(h,h') will take effect
opmin[child] = max( opmin[child] , opmax[node] );//If you decrease to height h on the child and then increase to
//height h' on the parent, with h'>h, then the first operation will lose effect
opmax[child] = min( opmax[child] , opmin[node] );//If you increase to height h on the child and then decrease to
// height h' on the parent, with h'<h, then the first operation will lose effect.
}
void push(int node,int l,int r){
if(l == r)
return ;
tochild(le,node);
tochild(ri,node);
opmax[node] = 0;
opmin[node] = MX;
}
void update(int node,int l,int r,int x,int y,int val,int type){//type 2 minimize 1 maximize
push(node,l,r);
if(l>r || r<x || l>y)
return ;
if(l>=x && r<=y){
if(type == 2)
opmin[node] = min(opmin[node],val),opmax[node] = min(opmax[node],val);
else
opmax[node] = max(opmax[node],val) , opmin[node] = max(opmin[node],val);
push(node,l,r);
return ;
}
update(le,l,mid,x,y,val,type);
update(ri,mid+1,r,x,y,val,type);
}
int query(int node,int l,int r,int idx){
push(node,l,r);
if(l == r)
return min(opmin[node],opmax[node]);
if(idx <= mid)
return query(le,l,mid,idx);
return query(ri,mid+1,r,idx);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,1,n);
for(int i=0;i<k;i++)
update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
for(int i=1;i<=n;i++)
finalHeight[i-1] = query(1,1,n,i);
}
