#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int N = 2000005;
int n, h, mx[N<<1], mn[N<<1];
void apply(int i, int lo, int hi) {
mn[i] = max(mn[i], lo);
mx[i] = max(mx[i], lo);
mn[i] = min(mn[i], hi);
mx[i] = min(mx[i], hi);
}
void push(int l, int r) {
int s = h;
for (l += n, r += n-1; s > 0; s--) {
for (int i = l >> s; i <= (r >> s); i++) {
apply(i<<1, mn[i], mx[i]);
apply(i<<1|1, mn[i], mx[i]);
mn[i] = 0, mx[i] = 100000;
}
}
}
void update(int l, int r, int lo, int hi) {
push(l, l+1);
push(r-1, r);
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) apply(l++, lo, hi);
if (r&1) apply(--r, lo, hi);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
::n = n;
h = __lg(n-1) + 1;
for (int i = 0; i < n; i++) mx[i] = 100000;
for (int i = 0; i < k; i++) {
if (op[i] == 1) update(left[i], right[i]+1, height[i], 100000);
else update(left[i], right[i]+1, 0, height[i]);
}
push(0, n);
for (int i = 0; i < n; i++) finalHeight[i] = mn[i+n];
return;
}
