#include "wall.h"
#include <bits/stdc++.h>
#define ar array
using namespace std;
const int N = 2e6 + 6;
ar <int, 2> t[N << 2];
int ans[N];
ar <int, 2> merge(const ar <int, 2> a, const ar <int, 2> b) {
int nl = max(a[0], b[0]), nr = min(a[1], b[1]);
ar <int, 2> res;
if (nl <= nr)
res = {nl, nr};
else if (nr < a[0])
res = {a[0], a[0]};
else
res = {a[1], a[1]};
return res;
}
void push(int v, int l, int r) {
if (l != r) {
t[v << 1] = merge(t[v], t[v << 1]);
t[v << 1 | 1] = merge(t[v], t[v << 1 | 1]);
t[v] = {0, N};
}
}
int ql, qr, qt, qx, tl, tr;
void update(int v, int l, int r) {
push(v, l, r);
if (ql <= l && r <= qr)
return t[v] = merge({tl, tr}, t[v]), void();
if (ql > r || l > qr)
return;
int m = l + r >> 1;
update(v << 1, l, m);
update(v << 1 | 1, m + 1, r);
}
void go(int v, int l, int r) {
push(v, l, r);
if (l == r)
return ans[l] = t[v][0], void();
int m = l + r >> 1;
go(v << 1, l, m);
go(v << 1 | 1, m + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
for (int i = 0; i < (N << 2); i++)
t[i] = {0, 0};
for (int i = 0; i < k; i++) {
ql = left[i], qr = right[i];
if (op[i] == 1)
tl = height[i], tr = N;
else
tl = 0, tr = height[i];
update(1, 0, n - 1);
}
go(1, 0, n - 1);
for (int i = 0; i < n; i++)
finalHeight[i] = ans[i];
}
