#include "wall.h"
#include <bits/stdc++.h>
#define ff(i,a,b) for (int i=a;i<b;i++)
#define bff(i,a,b) for (int i=b-1;i>=a;i--)
using namespace std;
const int mod=1000000007;
int k=1;
int val[4444444];
int l[4444444],r[4444444];
int minw[4444444],maxw[4444444];
void Build(int n)
{
while (k<n) k*=2;
ff(i,0,k) l[i+k]=i,r[i+k]=i;
bff(i,1,k) l[i]=l[2*i],r[i]=r[2*i+1];
ff(i,1,2*k) minw[i]=mod,maxw[i]=-mod;
}
void Upd(int p)
{
val[p]=min(val[p],minw[p]);
val[p]=max(val[p],maxw[p]);
if (p<k)
{
minw[2*p]=min(minw[2*p],minw[p]);
minw[2*p+1]=min(minw[2*p+1],minw[p]);
maxw[2*p]=min(maxw[2*p],minw[p]);
maxw[2*p+1]=min(maxw[2*p+1],minw[p]);
minw[2*p]=max(minw[2*p],maxw[p]);
minw[2*p+1]=max(minw[2*p+1],maxw[p]);
maxw[2*p]=max(maxw[2*p],maxw[p]);
maxw[2*p+1]=max(maxw[2*p+1],maxw[p]);
}
minw[p]=mod,maxw[p]=-mod;
}
void Minw(int p, int ll, int rr, int x)
{
if (ll>r[p] || rr<l[p]);
else if (ll<=l[p] && rr>=r[p]) minw[p]=min(minw[p],x),maxw[p]=min(maxw[p],x),Upd(p);
else Upd(p),Minw(2*p,ll,rr,x),Minw(2*p+1,ll,rr,x);
}
void Maxw(int p, int ll, int rr, int x)
{
if (ll>r[p] || rr<l[p]);
else if (ll<=l[p] && rr>=r[p]) maxw[p]=max(maxw[p],x),minw[p]=max(minw[p],x),Upd(p);
else Upd(p),Maxw(2*p,ll,rr,x),Maxw(2*p+1,ll,rr,x);
}
void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[])
{
Build(n);
ff(i,0,q)
{
if (op[i]==1) Maxw(1,left[i],right[i],height[i]);
else Minw(1,left[i],right[i],height[i]);
}
ff(i,1,2*k) Upd(i);
ff(i,0,n) finalHeight[i]=val[i+k];
}
