#include "wall.h"
#include <bits/stdc++.h>
#define pii pair <int,int>
#define f first
#define s second
#define pb push_back
#define leftt h*2,l,(l + r)/2
#define rightt h*2+1,(l + r)/2 + 1,r
using namespace std;
const int N = 2e6 + 3,inf = 1e9;
pii t[4*N],lz[4*N];
void chn(int h,int H,int tp){
if (tp == 1){
t[h].f = max(t[h].f,H);
t[h].s = max(t[h].s,H);
}else{
t[h].f = min(t[h].f,H);
t[h].s = min(t[h].s,H);
}
}
void push(int h){
if (t[h].f == 0 && t[h].s == inf) return;
chn(h*2,t[h].f,1);
chn(h*2,t[h].s,2);
chn(h*2+1,t[h].f,1);
chn(h*2+1,t[h].s,2);
t[h] = {0,inf};
}
void upd(int h,int l,int r,int L,int R,int H,int tp){
if (r < L || R < l) return ;
if (L <= l && r <= R){
chn(h,H,tp);
return;
}
push(h);
upd(leftt,L,R,H,tp);
upd(rightt,L,R,H,tp);
}
int get(int h,int l,int r,int idx){
if (l == r) return t[h].f;
push(h);
if (idx > (l + r)/2) return get(rightt,idx);
return get(leftt,idx);
}
void build(int h,int l,int r){
t[h] = {0,inf};
if (l == r) return;
build(leftt);
build(rightt);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
build(1,1,n);
for (int i = 0; i < k; i++){
upd(1,1,n,left[i] + 1,right[i] + 1,height[i],op[i]);
}
for (int i = 0; i < n; i++){
finalHeight[i] = get(1,1,n,i + 1);
}
return;
}
