#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N=2e6;
int a[N*4];
int add[N*4],rem[N*4];
void upd(int t, int l, int r, int ll, int rr, int op, int val){
if(ll>rr) return;
if(l==ll&&r==rr){
if(op==0) add[t]=max(add[t],val);
else{
if(~rem[t]){
rem[t]=min(rem[t],val);
}
else{
rem[t]=val;
}
}
}
else{
int m=(l+r)/2;
upd(t*2,l,m,ll,min(m,rr),op,val);
upd(t*2+1,m+1,r,max(ll,m+1),rr,op,val);
}
}
int get(int t, int l, int r, int idx){
if(~add[t]){
a[t]=max(add[t],a[t]);
add[t*2]=max(add[t*2],add[t]);
add[t*2+1]=max(add[t*2+1],add[t]);
}
if(~rem[t]){
a[t]=min(rem[t],a[t]);
if(~rem[t*2])rem[t*2]=min(rem[t*2],rem[t]);
else rem[t*2]=rem[t];
if(~rem[t*2+1])rem[t*2+1]=min(rem[t*2+1],rem[t]);
else rem[t*2+1]=rem[t];
}
if(l==r){
return a[t];
}
else{
int m=(l+r)/2;
if(idx<=m) return get(t*2,l,m,idx);
else return get(t*2+1,m+1,r,idx);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(rem,-1,sizeof rem);
for(int i=0;i<k;i++){
upd(1,0,n-1,left[i],right[i],op[i]-1,height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=get(1,0,n-1,i);
}
return;
}
