#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct T{
int l,r;
}st[8000001],lazy[8000001];
int res[2000001];
T operator +(T a, T b){
return {min(a.l,b.l),max(a.r,b.r)};
}
T operator *(T a, T b){
return {min(max(a.l,b.l),b.r),min(max(a.r,b.l),b.r)};
}
void down(int node, int l, int r){
if (l==r)
return;
st[node<<1]=st[node<<1]*lazy[node];
lazy[node<<1]=lazy[node<<1]*lazy[node];
st[node<<1|1]=st[node<<1|1]*lazy[node];
lazy[node<<1|1]=lazy[node<<1|1]*lazy[node];
lazy[node]={0,100000};
}
void update(int node, int l, int r, int u, int v, T t){
if (l>v||r<u||l>r)
return;
if (l>=u&&r<=v){
st[node]=st[node]*t;
lazy[node]=lazy[node]*t;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
update(node<<1,l,mid,u,v,t);
update(node<<1|1,mid+1,r,u,v,t);
st[node]=st[node<<1]+st[node<<1|1];
}
void dfs(int node, int l, int r){
if (l==r){
res[l]=st[node].l;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
dfs(node<<1,l,mid);
dfs(node<<1|1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i=0;i<=n*4;i++)
lazy[i]={0,100000};
for (int i=0;i<k;i++){
T t;
if (op[i]==1)
t={height[i],100000};
else
t={0,height[i]};
update(1,0,n-1,left[i],right[i],t);
}
dfs(1,0,n-1);
for (int i=0;i<n;i++)
finalHeight[i]=res[i];
return;
}
