#include <bits/stdc++.h>
#include "wall.h"
const int N = 2e6+10;
int op(int o, int a, int b){
return (o == 1 ? std::max(a, b) : std::min(a, b));
}
struct lazy_seg{
int seg[4*N];
std::pair<int, int> lazy[4*N];
lazy_seg(){
std::memset(seg, 0, sizeof seg);
for(int i = 0; i < 4*N; ++i) lazy[i] = {-1, -1};
}
void push(int p, int l, int r){
if(l > r || lazy[p] == std::make_pair(-1, -1)) return;
if(l != r){
seg[p*2] = op(lazy[p].first, seg[p*2], lazy[p].second);
seg[p*2+1] = op(lazy[p].first, seg[p*2+1], lazy[p].second);
lazy[p*2] = lazy[p*2+1] = lazy[p];
}
lazy[p] = {-1, -1};
}
void upd(int p, int l, int r, int wl, int wr, int val, int o){
if(l > r || l > wr || r < wl) return;
push(p, l, r);
if(wl <= l && r <= wr){
seg[p] = op(o, val, seg[p]);
lazy[p] = {o, val};
push(p, l, r);
return;
}
int mid = (l+r)>>1;
upd(p*2, l, mid, wl, wr, val, o);
upd(p*2+1, mid+1, r, wl, wr, val, o);
seg[p] = op(3-o, seg[p*2], seg[p*2+1]);
}
int get(int idx, int p, int l, int r){
push(p, l, r);
if(l == r) return seg[p];
int mid = (l+r)>>1;
if(idx <= mid) return get(idx, p*2, l, mid);
return get(idx, p*2+1, mid+1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
lazy_seg seg;
for(int i = 0; i < k; ++i){
seg.upd(1, 1, n, left[i]+1, right[i]+1, height[i], op[i]);
}
for(int i = 1; i <= n; ++i){
finalHeight[i-1] = seg.get(i, 1, 1, n);
}
}
