#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN=2e6;
const int INF=1e9+7;
struct Node{
int mn;
int mx;
};
Node tree[4*MAXN];
void build(int node,int l,int r){
tree[node].mn=INF;
tree[node].mx=-INF;
if(l==r) return;
int mid=(l+r)/2;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
}
void push(int node,int l,int r){
if(l==r) return;
int left=node<<1;
int right=left|1;
tree[left].mn=min(tree[node].mn,tree[left].mn);
tree[left].mn=max(tree[node].mx,tree[left].mn);
tree[left].mx=min(tree[node].mn,tree[left].mx);
tree[left].mx=max(tree[node].mx,tree[left].mx);
tree[right].mn=min(tree[node].mn,tree[right].mn);
tree[right].mn=max(tree[node].mx,tree[right].mn);
tree[right].mx=min(tree[node].mn,tree[right].mx);
tree[right].mx=max(tree[node].mx,tree[right].mx);
// tree[node].mn=INF;
// tree[node].mx=-INF;
}
void update(int node,int l,int r,int ql,int qr,int x,int t){
push(node,l,r);
if(ql>r||qr<l) return;
if(ql<=l&&r<=qr){
if(t){
tree[node].mn=min(tree[node].mn,x);
tree[node].mx=min(tree[node].mx,x);
}
else{
tree[node].mn=max(tree[node].mn,x);
tree[node].mx=max(tree[node].mx,x);
}
return;
}
tree[node].mn=INF;
tree[node].mx=-INF;
int mid=(l+r)/2;
update(node<<1,l,mid,ql,qr,x,t);
update(node<<1|1,mid+1,r,ql,qr,x,t);
}
void query(int node,int l,int r,int finalHeight[]){
if(l==r){
finalHeight[l-1]=tree[node].mn;
return;
}
push(node,l,r);
int mid=(l+r)/2;
query(node<<1,l,mid,finalHeight);
query(node<<1|1,mid+1,r,finalHeight);
}
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,1,n,left[i]+1,right[i]+1,height[i],op[i]-1);
}
// for(int i=0;i<n;i++){
// int x=query(1,1,n,i);
// cout<<x<<" ";
// finalHeight[i]=x;
// }
// cout<<endl;
query(1,1,n,finalHeight);
for(int i=0;i<n;i++){
// cout<<finalHeight[i]<<" ";
}
// cout<<endl;
return;
}
