#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 1e6;
vector<int64_t>tree(4*MXN);
vector<int64_t>lazy(4*MXN);
int64_t func(int64_t a,int64_t b){
return min(a,b);
}
void build(int64_t node,int64_t node_low,int64_t node_high){
if (node_low==node_high){
tree[node]=0;
}
else {
int64_t mid =(node_low+node_high)>>1;
build(node*2,node_low,mid);
build(node*2 + 1,mid+1,node_high);
tree[node]=func(tree[node*2],tree[node*2 + 1]);
}
}
void push(int64_t x){
tree[x + x] = min(tree[x],tree[x+x]);
tree[x + x + 1] = min(tree[x],tree[x+x + 1]);
}
void update(int64_t node,int64_t node_low,int64_t node_high,int64_t q_low,int64_t q_high,int64_t new_val,int ok){
if (node_low>node_high||node_low>q_high||node_high<q_low)return;
if (q_low<=node_low&&q_high>=node_high){
if (ok==1){
tree[node] = max(tree[node],new_val);
}
else{
tree[node] = min(tree[node],new_val);
}
return ;
}
push(node);
int64_t mid = (node_low + node_high)/2;
update(node*2,node_low,mid,q_low,q_high,new_val,ok);
update(node*2 + 1,mid + 1,node_high,q_low,q_high,new_val,ok);
tree[node]= func(tree[node*2],tree[node*2 + 1]);
}
int64_t query(int64_t node,int64_t node_low,int64_t node_high,int64_t query_low,int64_t query_high){
if (node_low>node_high||node_low>query_high||node_high<query_low)return INT_MAX;
if (query_low<=node_low&&query_high>=node_high){
return tree[node];
}
int64_t mid = (node_low+node_high)/2;
return func(query(node*2,node_low,mid,query_low,query_high),query(node*2 + 1,mid+1,node_high,query_low,query_high));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,0,n-1);
for (int i =0;i<k;++i){
update(1,0,n-1,left[i],right[i],height[i],op[i]);
}
for (int i = 0;i<n;++i){
finalHeight[i] = query(1,0,n-1,i,i);
}
}
