#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
void chmax(int &x, const int &y){ x = max(x, y); }
void chmin(int &x, const int &y){ x = min(x, y); }
const int inf = 1e8;
struct SegTree{
struct Info{
int mn1, mn2, mx1, mx2;
Info() : mn1(0), mn2(inf), mx1(0), mx2(-inf) {}
void merge(Info lf, Info rg){
mx2 = -inf, mn2 = inf;
mn1 = min(lf.mn1, rg.mn1);
mx1 = max(lf.mx1, rg.mx1);
for ( auto x: {lf.mx1, lf.mx2, rg.mx1, rg.mx2} ){
if ( x != mx1 ) chmax(mx2, x);
}
for ( auto x: {lf.mn1, lf.mn2, rg.mn1, rg.mn2} ){
if ( x != mn1 ) chmin(mn2, x);
}
}
};
vector <Info> seg;
vector <int> lmx, lmn;
int n;
SegTree(int n) : seg(n * 4 + 5), lmx(n * 4 + 5, -inf), lmn(n * 4 + 5, inf), n(n) {}
void push(int v, int l, int r){
if ( l != r ){
for ( auto x: {v * 2, v * 2 + 1} ){
chmin(lmn[x], lmn[v]);
chmax(lmx[x], lmx[v]);
}
}
if ( seg[v].mx1 == seg[v].mn1 ){
if ( lmn[v] < seg[v].mx1 ){
seg[v].mx1 = seg[v].mn1 = lmn[v];
} else{
seg[v].mx1 = seg[v].mn1 = max(seg[v].mn1, lmx[v]);
}
} else{
if ( seg[v].mn1 == seg[v].mx2 ){
seg[v].mn1 = seg[v].mx2 = max(seg[v].mn1, lmx[v]);
} else chmax(seg[v].mn1, lmx[v]);
if ( seg[v].mx1 == seg[v].mn2 ){
seg[v].mx1 = seg[v].mn2 = min(seg[v].mx1, lmn[v]);
} else chmin(seg[v].mx1, lmn[v]);
}
lmn[v] = inf, lmx[v] = -inf;
}
void upd_mx(int v, int l, int r, int tl, int tr, int x){
push(v, l, r);
if ( l > tr || r < tl || seg[v].mn1 >= x ) return;
if ( tl <= l && tr >= r && seg[v].mn2 > x ){
lmx[v] = x;
push(v, l, r);
return;
}
int m = (l + r) / 2;
upd_mx(v * 2, l, m, tl, tr, x);
upd_mx(v * 2 + 1, m + 1, r, tl, tr, x);
seg[v].merge(seg[v * 2], seg[v * 2 + 1]);
}
void ckmax(int l, int r, int x){
upd_mx(1, 0, n - 1, l, r, x);
}
void upd_mn(int v, int l, int r, int tl, int tr, int x){
push(v, l, r);
if ( l > tr || r < tl || seg[v].mx1 <= x ) return;
if ( tl <= l && tr >= r && seg[v].mx2 < x ){
lmn[v] = x;
push(v, l, r);
return;
}
int m = (l + r) / 2;
upd_mn(v * 2, l, m, tl, tr, x);
upd_mn(v * 2 + 1, m + 1, r, tl, tr, x);
seg[v].merge(seg[v * 2], seg[v * 2 + 1]);
}
void ckmin(int l, int r, int x){
upd_mn(1, 0, n - 1, l, r, x);
}
int get(int v, int l, int r, int x){
push(v, l, r);
if ( l == r ) return seg[v].mx1;
int m = (l + r) / 2;
if ( x <= m ) return get(v * 2, l, m, x);
return get(v * 2 + 1, m + 1, r, x);
}
int qry(int x){ return get(1, 0, n - 1, x); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
SegTree seg(n);
for ( int i = 0; i < k; i++ ){
if ( op[i] == 1 ) seg.ckmax(left[i], right[i], height[i]);
else seg.ckmin(left[i], right[i], height[i]);
}
for ( int i = 0; i < n; i++ ){
finalHeight[i] = seg.qry(i);
}
}
