#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int maxN=2000100;
int L,R,H,C;
int Mx[maxN*4],Mi[maxN*4],fH[maxN];
inline int ls(int p){return p*2+1;}
inline int rs(int p){return p*2+2;}
void Max(int p,int k){
if (Mx[p]<k)Mx[p]=k;
if (Mi[p]<k)Mi[p]=k;
}
void Min(int p,int k){
if (Mx[p]>k)Mx[p]=k;
if (Mi[p]>k)Mi[p]=k;
}
void push_node(int p){
Max(ls(p),Mx[p]);
Min(ls(p),Mi[p]);
Max(rs(p),Mx[p]);
Min(rs(p),Mi[p]);
Mx[p]=0;
Mi[p]=0x7fffffff;
}
void update(int p,int l,int r){
if (L<=l&&r<=R){
if (C==1)Max(p,H);
else Min(p,H);
return;
}
push_node(p);
int m=(l+r)/2;
if (L<=m)update(ls(p),l,m);
if (m<R)update(rs(p),m+1,r);
return;
}
void query(int p,int l,int r){
if(l==r){fH[l]=Mx[p];return;}
int m=(l+r)/2;
push_node(p);
query(ls(p),l,m);
query(rs(p),m+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
memset(Mx,0,sizeof(Mx));
memset(Mi,0x7f,sizeof(Mi));
for (int i=0;i<k;i++){
L=left[i];
R=right[i];
H=height[i];
C=op[i];
update(0,0,n-1);
}
query(0,0,n-1);
for (int i=0;i<n;i++)finalHeight[i]=fH[i];
return;
}
