#include "wall.h"
#include<iostream>
using namespace std;
const int N = 2e6 + 123;
const int inf = 1e9 + 123;
int n;
int fl[N << 2], fr[N << 2];
void build(int l = 0, int r = n, int v = 1) {
fl[v] = 0, fr[v] = inf;
if (r - l == 1) return;
int m = (l + r) >> 1;
build(l, m, v << 1);
build(m, r, v<<1|1);
}
void make(int &al, int &ar, int bl, int br) {
if (ar < bl) {
al = bl, ar = bl;
} else if (br < al) {
al = br, ar = br;
} else {
al = max(al, bl);
ar = min(ar, br);
}
}
void push(int v, int l, int r) {
if (r - l > 1) {
make(fl[v << 1], fr[v << 1], fl[v], fr[v]);
make(fl[v<<1|1], fr[v<<1|1], fl[v], fr[v]);
fl[v] = 0, fr[v] = inf;
}
}
void upd(int L, int R, int cl, int cr, int l = 0, int r = n, int v = 1) {
push(v, l, r);
if (L <= l && r <= R) {
make(fl[v], fr[v], cl, cr);
push(v, l, r);
return;
}
if (L >= r || l >= R) return;
int m = (l + r) >> 1;
upd(L, R, cl, cr, l, m, v << 1);
upd(L, R, cl, cr, m, r, v<<1|1);
}
int a[N];
void show(int l = 0, int r = n, int v = 1) {
push(v, l, r);
if (r - l == 1) {
a[l] = fl[v];
//cout << "[" << fl[v] << ", " << fr[v] << "] ";
return;
}
int m = (l + r) >> 1;
show(l, m, v << 1);
show(m, r, v<<1|1);
}
void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = n_;
build();
for (int i = 0 ; i < k ; ++ i) {
if (op[i] == 1) {
upd(left[i], right[i] + 1, height[i], inf);
} else {
upd(left[i], right[i] + 1, 0, height[i]);
}
}
show();
for (int i = 0 ; i < n ; ++ i) {
finalHeight[i] = a[i];
}
}
