#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e6+5;
int seg[4*mxN], L[4*mxN], R[4*mxN];
void push(int u) {
seg[u<<1] = max(seg[u<<1], L[u]);
seg[u<<1] = min(seg[u<<1], R[u]);
L[u<<1] = max(L[u<<1], L[u]);
L[u<<1] = min(L[u<<1], R[u]);
R[u<<1] = min(R[u<<1], R[u]);
R[u<<1] = max(R[u<<1], L[u]);
seg[u<<1|1] = max(seg[u<<1|1], L[u]);
seg[u<<1|1] = min(seg[u<<1|1], R[u]);
L[u<<1|1] = max(L[u<<1|1], L[u]);
L[u<<1|1] = min(L[u<<1|1], R[u]);
R[u<<1|1] = min(R[u<<1|1], R[u]);
R[u<<1|1] = max(R[u<<1|1], L[u]);
L[u] = INT_MIN, R[u] = INT_MAX;
}
void upd(int l, int r, int x, int y, int Lx, int Rx, int u) {
if (x <= l && r <= y) {
seg[u] = max(Lx, seg[u]);
seg[u] = min(Rx, seg[u]);
L[u] = max(L[u], Lx);
L[u] = min(L[u], Rx);
R[u] = min(R[u], Rx);
R[u] = max(R[u], Lx);
} else {
push(u);
int m = l + (r-l)/2;
if (m >= x) upd(l, m, x, y, Lx, Rx, u<<1);
if (m+1 <= y) upd(m+1, r, x, y, Lx, Rx, u<<1|1);
}
}
int qr(int l, int r, int x, int u) {
if (l == r) return seg[u];
else {
push(u);
int m = l + (r-l)/2;
if (m >= x) return qr(l, m, x, u<<1);
else return qr(m+1, r, x, u<<1|1);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (auto &e : L) e = INT_MIN;
for (auto &e : R) e = INT_MAX;
for (int i = 0; i < k; i++) {
if (op[i] == 1) upd(0, n-1, left[i], right[i], height[i], INT_MAX, 1);
else upd(0, n-1, left[i], right[i], INT_MIN, height[i], 1);
}
for (int i = 0; i < n; i++) finalHeight[i] = qr(0, n-1, i, 1);
}
