#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int MAX = 2000020;
int n, ans[MAX];
struct segtree {
pair<int, int> st[MAX << 2];
void build(int id, int l, int r) {
st[id] = make_pair(-INF, INF);
if (l == r) {
st[id] = make_pair(0, 0);
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
}
void update(int id, int l, int r) {
if (st[id].first > r) st[id] = make_pair(r, r); else
if (st[id].second < l) st[id] = make_pair(l, l); else
st[id] = make_pair(max(l, st[id].first), min(r, st[id].second));
}
void push(int id) {
update(id << 1, st[id].first, st[id].second);
update(id << 1 | 1, st[id].first, st[id].second); st[id] = make_pair(-INF, INF);
}
void update(int id, int l, int r, int u, int v, int t, int newH) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
if (!t) update(id, newH, INF);
else update(id, -INF, newH);
return;
}
int mid = l + r >> 1; push(id);
update(id << 1, l, mid, u, v, t, newH);
update(id << 1 | 1, mid + 1, r, u, v, t, newH);
}
} tree;
void magic(int id, int l, int r) {
if (l == r) {
ans[l] = tree.st[id].first;
return;
}
int mid = l + r >> 1; tree.push(id);
magic(id << 1, l, mid); magic(id << 1 | 1, mid + 1, r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
tree.build(1, 1, n);
for (int i = 0; i < k; i++) {
tree.update(1, 1, n, left[i] + 1, right[i] + 1, op[i] - 1, height[i]);
}
magic(1, 1, n);
for (int i = 0; i < n; ++i)
finalHeight[i] = ans[i + 1];
}
