#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
vector<long>mx1,mx2,mn1,mn2;
void update_add(long l,long r,long nl,long nr,long node,long val)
{
if(l>nr||r<nl||val<=mn1[node]){
return;
}
if(val<mn2[node]){
mn1[node]=val;
return;
}
update_add(l,r,nl,(nl+nr)/2,node*2,val);
update_add(l,r,((nl+nr)/2)+1,nr,(node*2)+1,val);
mn1[node]=min(mn1[node*2],mn1[(node*2)+1]);
mn2[node]=1e9;
if(mn1[node*2]>mn1[node]){
mn2[node]=min(mn2[node],mn1[node*2]);
}
if(mn1[(node*2)+1]>mn1[node]){
mn2[node]=min(mn2[node],mn1[(node*2)+1]);
}
mn2[node]=min(mn2[node],mn2[node*2]);
mn2[node]=min(mn2[node],mn2[(node*2)+1]);
}
void update_remove(long l,long r,long nl,long nr,long node,long val)
{
if(l>nr||r<nl||val>=mx1[node]){
return;
}
if(val>mx2[node]){
mx1[node]=val;
return;
}
update_remove(l,r,nl,(nl+nr)/2,node*2,val);
update_remove(l,r,((nl+nr)/2)+1,nr,(node*2)+1,val);
mx1[node]=max(mx1[node*2],mx1[(node*2)+1]);
mx2[node]=-1e9;
if(mx1[node*2]<mx1[node]){
mx2[node]=max(mn2[node],mx1[node*2]);
}
if(mx1[(node*2)+1]>mx1[node]){
mx2[node]=max(mx2[node],mx1[(node*2)+1]);
}
mx2[node]=min(mx2[node],mx2[node*2]);
mx2[node]=min(mx2[node],mx2[(node*2)+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
long N=n;
while(N&(N-1)){
N=N&(N-1);
}
N*=2;
mx1.resize(2*N);
mx2.resize(2*N);
mn1.resize(2*N);
mn2.resize(2*N);
for(int i=0;i<2*N;i++){
mx1[i]=0;
mx1[i]=-1e9;
mn1[i]=0;
mn2[i]=1e9;
}
for(int i=0;i<k;i++){
if(op[i]==1){
update_add(left[i],right[i],0,N-1,1,height[i]);
continue;
}
update_remove(left[i],right[i],0,N-1,1,height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=mx1[N+i];
}
return;
}
