#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2000001;
int mn[4 * N], mx[4 * N];
int n, k;
void upd(int MN, int MX, int now) {
mn[now] = max(MN, min(mn[now], mx[now]));
mx[now] = min(MX, max(mn[now], mx[now]));
}
void push(int now) {
upd(mn[now], mx[now], 2 * now);
upd(mn[now], mx[now], 2 * now + 1);
mn[now] = 0, mx[now] = 1e9;
}
void build(int now = 1, int l = 1, int r = n) {
mn[now] = 0;
mx[now] = 1e9;
if (l == r) return;
int mid = (l + r) / 2;
build(2 * now, l, mid);
build(2 * now + 1, mid + 1, r);
}
void update(int ql, int qr, int w, int op, int now = 1, int l = 1, int r = n) {
if (l > qr || r < ql) return;
if (ql <= l && r <= qr) {
if (op == 1) upd(w, 1e9, now);
else upd(0, w, now);
return;
}
push(now);
int mid = (l + r) / 2;
update(ql, qr, w, op, 2 * now, l, mid);
update(ql, qr, w, op, 2 * now + 1, mid + 1, r);
}
void cal(int finalHeight[], int now = 1, int l = 1, int r = n) {
if (l == r) {
finalHeight[l - 1] = min(mn[now], mx[now]);
return;
}
push(now);
int mid = (l + r) / 2;
cal(finalHeight, 2 * now, l, mid);
cal(finalHeight, 2 * now + 1, mid + 1, r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = N, k = K;
build();
for (int i = 0;i < k;i++) {
update(left[i] + 1, right[i] + 1, height[i], op[i]);
// cal(finalHeight);
// for (int i = 0;i < n;i++) {
// cout << finalHeight[i] << ' ';
// }
// cout << '\n';
}
cal(finalHeight);
}
