#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 6;
int mn[N * 2], mx[N * 2];
void build(int nd, int l, int r) {
if (l == r) {
return;
}
mn[nd] = N;
mx[nd] = 0;
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
build(nd + 1, l, mid);
build(rs, mid + 1, r);
}
void push(int nd, int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
for (int i : {nd + 1, rs}) {
mx[i] = max(mx[i], mx[nd]);
mn[i] = max(mn[i], mx[nd]);
mx[i] = min(mx[i], mn[nd]);
mn[i] = min(mn[i], mn[nd]);
}
mn[nd] = N; mx[nd] = 0;
}
void upd(int nd, int l, int r, int s, int e, int v, bool maximize) {
push(nd, l, r);
if (l >= s && r <= e) {
if (maximize) {
mx[nd] = max(mx[nd], v);
mn[nd] = max(mn[nd], v);
} else {
mx[nd] = min(mx[nd], v);
mn[nd] = min(mn[nd], v);
}
push(nd, l, r);
return;
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (mid >= e) {
upd(nd + 1, l, mid, s, e, v, maximize);
} else {
if (mid < s) {
upd(rs, mid + 1, r, s, e, v, maximize);
} else {
upd(nd + 1, l, mid, s, e, v, maximize);
upd(rs, mid + 1, r, s, e, v, maximize);
}
}
}
int qry(int nd, int l, int r, int p) {
push(nd, l, r);
if (l == r) {
return mx[nd];
}
int mid = (l + r) >> 1;
int rs = nd + ((mid - l + 1) << 1);
if (p <= mid) {
return qry(nd + 1, l, mid, p);
} else {
return qry(rs, mid + 1, r, p);
}
}
void buildWall(int n, int q, int op[], int l[], int r[], int v[], int finalHeight[]) {
build(0, 0, n - 1);
for (int i = 0; i < q; ++i) {
upd(0, 0, n - 1, l[i], r[i], v[i], op[i] % 2);
}
for (int i = 0; i < n; ++i) {
finalHeight[i] = qry(0, 0, n - 1, i);
}
return;
}
