#include <bits/stdc++.h>
#include "wall.h"
const int N = 2e6+10;
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] = {0, INT_MAX};
}
void push(int p, int l, int r){
if(l > r || lazy[p] == std::make_pair(0, INT_MAX)) return;
if(l != r){
seg[p*2] = std::max(seg[p*2], lazy[p].first), seg[p*2] = std::min(seg[p*2], lazy[p].second);
lazy[p*2].first = std::max(lazy[p*2].first, lazy[p].first), lazy[p*2].first = std::min(lazy[p*2].first, lazy[p].second);
lazy[p*2].second = std::min(lazy[p*2].second, lazy[p].second), lazy[p*2].second = std::max(lazy[p*2].second, lazy[p].first);
seg[p*2+1] = std::max(seg[p*2+1], lazy[p].first), seg[p*2+1] = std::min(seg[p*2+1], lazy[p].second);
lazy[p*2+1].first = std::max(lazy[p*2+1].first, lazy[p].first), lazy[p*2+1].first = std::min(lazy[p*2+1].first, lazy[p].second);
lazy[p*2+1].second = std::min(lazy[p*2+1].second, lazy[p].second), lazy[p*2+1].second = std::max(lazy[p*2+1].second, lazy[p].first);
}
lazy[p] = {0, INT_MAX};
}
void upd(int p, int l, int r, int wl, int wr, int lo, int hi){
if(l > r || l > wr || r < wl) return;
push(p, l, r);
if(wl <= l && r <= wr){
seg[p] = std::max(seg[p], lo);
seg[p] = std::min(seg[p], hi);
lazy[p].first = std::max(lazy[p].first, lo);
lazy[p].first = std::min(lazy[p].first, hi);
lazy[p].second = std::min(lazy[p].second, hi);
lazy[p].second = std::max(lazy[p].second, lo);
push(p, l, r);
return;
}
int mid = (l+r)>>1;
upd(p*2, l, mid, wl, wr, hi, lo);
upd(p*2+1, mid+1, r, wl, wr, hi, lo);
}
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){
if(op[i] == 1) seg.upd(1, 1, n, left[i]+1, right[i]+1, height[i], INT_MAX);
if(op[i] == 2) seg.upd(1, 1, n, left[i]+1, right[i]+1, 0, height[i]);
}
for(int i = 1; i <= n; ++i){
finalHeight[i-1] = seg.get(i, 1, 1, n);
}
}
