#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
int const N=2e6+5;
int const inf=1e5;
int rise[4*N];
int down[4*N];
void up_to_date(int node,int l,int r){
if(l+1==r)
return;
if(rise[node]>0){
int h=rise[node];
rise[node]=0;
rise[node*2]=max(h,rise[node*2]);
down[node*2]=max(down[node*2],rise[node*2]);
rise[node*2+1]=max(h,rise[node*2+1]);
down[node*2+1]=max(down[node*2+1],rise[node*2+1]);
}
if(down[node]<inf){
int h=down[node];
down[node]=inf;
if(l+1<r){
down[node*2]=min(h,down[node*2]);
rise[node*2]=min(rise[node*2],down[node*2]);
down[node*2+1]=min(h,down[node*2+1]);
rise[node*2+1]=min(rise[node*2+1],down[node*2+1]);
}
}
}
void update(int node,int s,int e,int l,int r,int h,int t){
if(e<=l || r<=s)
return;
// cout<<node<<' '<<s<<' '<<e-1<<endl;
// cout<<rise[node]<<' '<<down[node]<<endl;
up_to_date(node,s,e);
if(l<=s && e<=r){
if(t==1){
rise[node]=max(h,rise[node]);
down[node]=max(down[node],rise[node]);
}
else{
down[node]=min(h,down[node]);
rise[node]=min(rise[node],down[node]);
}
// cout<<"leave"<<endl;
// cout<<rise[node]<<' '<<down[node]<<endl;
// cout<<endl;
}
else{
int mid=(s+e)/2;
update(node*2,s,mid,l,r,h,t);
update(node*2+1,mid,e,l,r,h,t);
}
}
void printing(int node,int l,int r){
// cout<<"**"<<endl;
// cout<<l<<' '<<r-1<<endl;
// cout<<rise[node]<<' '<<down[node]<<endl;
if(l+1==r)
return;
int mid=(l+r)/2;
printing(node*2,l,mid);
printing(node*2+1,mid,r);
}
int query(int node,int s,int e,int p){
up_to_date(node,s,e);
if(s+1==e)
return rise[node];
int mid=(s+e)/2;
if(p<mid)
return query(node*2,s,mid,p);
else
return query(node*2+1,mid,e,p);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < 4*N; ++i){
down[i]=inf;
rise[i]=0;
}
for (int i = 0; i < k; ++i){
// cout<<endl;
update(1,0,n,left[i],right[i]+1,height[i],op[i]);
// printing(0,0,n);
}
for (int i = 0; i < n; ++i)
finalHeight[i]=query(1,0,n,i);
}
