#include "wall.h"
# include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 2;
struct st{
int mn, mx;
st(){
mx = 0;
mn = 1e5 + 1;
}
}t[N * 4];
int n;
void upd(int v, int x, int tp){
if(tp == 1){
t[v].mx = max(t[v].mx, x);
t[v].mn = max(t[v].mn, x);
} else {
t[v].mn = min(t[v].mn, x);
t[v].mx = min(t[v].mx, x);
}
}
void down(int v){
upd(v << 1, t[v].mx, 1);
upd(v << 1, t[v].mn, 2);
upd((v << 1) | 1, t[v].mx, 1);
upd((v << 1) | 1, t[v].mn, 2);
t[v].mx = 0;
t[v].mn = 1e5 + 1;
}
void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
if(l <= tl && tr <= r){
upd(v, x, tp);
return ;
}
if(tl > r || l > tr) return ;
down(v);
int tm = (tl + tr) >> 1;
update(l, r, x, tp, v << 1, tl, tm);
update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}
int get(int pos, int v = 1, int tl = 1, int tr = n){
if(tl == tr){
return t[v].mx;
}
down(v);
int tm = (tl + tr) >> 1;
if(pos <= tm)
return get(pos, v << 1, tl, tm);
return get(pos, (v << 1) | 1, tm + 1, tr);
}
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = N;
for(int i = 0; i < k; i ++){
update(left[i] + 1, right[i] + 1, height[i], op[i]);
}
for(int i = 0; i < n; i ++){
finalHeight[i] = get(i + 1);
}
}
