#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pll;
#define X first
#define Y second
const int MAXN = 1e7 + 10;
pll sg[MAXN];
int n, lz[MAXN], A[MAXN];
inline pll merge(pll a, pll b) {
a.X = min(a.X, b.X);
a.Y = max(a.Y, b.Y);
return a;
}
void build(int l = 0, int r = n - 1, int v = 1) {
lz[v] = -1;
if (l == r) sg[v] = {0, 0};
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
}
}
inline void push(int v) {
if (lz[v] >= 0) {
sg[v] = {lz[v], lz[v]};
if ((v << 1 | 1) < MAXN) lz[v << 1] = lz[v << 1 | 1] = lz[v];
}
lz[v] = -1;
}
void q_max(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
push(v);
if (ql > r || qr < l || sg[v].X >= val) return;
if (ql <= l && qr >= r) {
if (sg[v].Y <= val) {
lz[v] = val;
push(v);
return;
}
}
int mid = (l + r) >> 1;
q_max(ql, qr, val, l, mid, v << 1);
q_max(ql, qr, val, mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
return;
}
void q_min(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
push(v);
if (ql > r || qr < l || sg[v].Y <= val) return;
if (ql <= l && qr >= r) {
if (sg[v].X >= val) {
lz[v] = val;
push(v);
return;
}
}
int mid = (l + r) >> 1;
q_min(ql, qr, val, l, mid, v << 1);
q_min(ql, qr, val, mid + 1, r, v << 1 | 1);
sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
return;
}
void print(int l = 0, int r = n - 1, int v = 1) {
push(v);
if (l == r) {
A[l] = sg[v].X;
return;
}
int mid = (l + r) >> 1;
print(l, mid, v << 1);
print(mid + 1, r, v << 1 | 1);
}
void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
n = n_;
build();
for (int i = 0; i < k; i++) {
if (op[i] == 1) q_max(left[i], right[i], height[i]);
else q_min(left[i], right[i], height[i]);
}
print();
for (int i = 0; i < n; i++) finalHeight[i] = A[i];
return;
}
