#include "wall.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sz() size()
#define fr first
#define sc second
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
//#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
using namespace std;
const int nmax=2000005;
int up[4*nmax],down[4*nmax],ans[nmax],lazy[4*nmax];
void lazi(int nod,int up1,int down1){
down[nod]=max(down[nod],down1);
down[nod]=min(down[nod],up1);
up[nod]=min(up[nod],up1);
up[nod]=max(up[nod],down1);
}
void update(int l,int r,int le,int ri,int op,int h,int nod){
if(l>ri || r<le) return;
else if(l>=le && r<=ri){
if(op==1){
up[nod]=max(up[nod],h);
down[nod]=max(down[nod],h);
}
else{
up[nod]=min(up[nod],h);
down[nod]=min(down[nod],h);
}
}
else{
lazi(2*nod,up[nod],down[nod]);
lazi(2*nod+1,up[nod],down[nod]);
int mid=l+(r-l)/2;
update(l,mid,le,ri,op,h,2*nod);
update(mid+1,r,le,ri,op,h,2*nod+1);
down[nod]=0;
up[nod]=1e18;
}
}
void complete(int l,int r,int nod){
if(l!=r){
int mid=l+(r-l)/2;
lazi(2*nod,up[nod],down[nod]);
lazi(2*nod+1,up[nod],down[nod]);
complete(l,mid,2*nod);
complete(mid+1,r,2*nod+1);
}
else{
ans[l]=up[nod];
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=1;i<=k;i++){
update(1,n,left[i-1]+1,right[i-1]+1,op[i-1],height[i-1],1);
}
complete(1,n,1);
for(int i=1;i<=n;i++) finalHeight[i-1]=ans[i];
}
