#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int inf = (int) 1e6;
class node {
public:
int l, r;
node(int l = 0, int r = inf): l(l), r(r) {
}
void apply(const node &v) {
int ll = v.l, rr = v.r;
if (r < ll) {
l = r = ll;
} else if (l > rr) {
l = r = rr;
} else {
l = max(l, ll);
r = min(r, rr);
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
vector<node> tree(n * 2 - 1);
function<void(int, int, int, int, int, node)> modify = [&](int x, int l, int r, int ll, int rr, node v) {
if (ll <= l && r <= rr) {
tree[x].apply(v);
} else {
int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
tree[x + 1].apply(tree[x]);
tree[z].apply(tree[x]);
tree[x] = node();
if (ll <= y) {
modify(x + 1, l, y, ll, rr, v);
}
if (rr > y) {
modify(z, y + 1, r, ll, rr, v);
}
}
};
function<void(int, int, int)> push = [&](int x, int l, int r) {
if (l == r) {
finalHeight[l] = tree[x].l;
} else {
int y = (l + r) >> 1, z = x + ((y - l + 1) << 1);
tree[x + 1].apply(tree[x]);
tree[z].apply(tree[x]);
tree[x] = node();
push(x + 1, l, y);
push(z, y + 1, r);
}
};
for (int i = 0; i < k; ++i) {
if (op[i] == 1) {
modify(0, 0, n - 1, left[i], right[i], node(height[i], inf));
} else {
modify(0, 0, n - 1, left[i], right[i], node(0, height[i]));
}
}
push(0, 0, n - 1);
}
