#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTreeMax {
int n;
vector<int> t, lazy;
SegmentTreeMax(int n) : n(n), t((n << 2) + 1, 0), lazy((n << 2) + 1, -1) {}
void propogate(int v, int vl, int vr) {
if (lazy[v] == -1) return;
t[v] = lazy[v];
if (vl != vr) {
lazy[2 * v + 1] = lazy[2 * v + 2] = lazy[v];
}
lazy[v] = -1;
}
void update(int l, int r, int x, int v, int vl, int vr) {
propogate(v, vl, vr);
if (l > vr || vl > r) return;
else if (l <= vl && vr <= r) {
lazy[v] = x;
propogate(v, vl, vr);
} else {
int vm = (vl + vr) >> 1;
update(l, r, x, v << 1, vl, vm);
update(l, r, x, v << 1 | 1, vm + 1, vr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
}
}
int query(int l, int r, int v, int vl, int vr) {
propogate(v, vl, vr);
if (l > vr || vl > r) return INT_MIN;
else if (l <= vl && vr <= r) return t[v];
else {
int vm = (vl + vr) >> 1;
int L = query(l, r, v << 1, vl, vm);
int R = query(l, r, v << 1 | 1, vm + 1, vr);
t[v] = max(t[v << 1], t[v << 1 | 1]);
return max(L, R);
}
}
void update(int l, int r, int x) {
update(l, r, x, 1, 0, n - 1);
}
int query(int l, int r) {
return query(l, r, 1, 0, n - 1);
}
};
struct SegmentTreeMin {
int n;
vector<int> t, lazy;
SegmentTreeMin(int n) : n(n), t((n << 2) + 1, INT_MAX), lazy((n << 2) + 1, -1) {}
void propogate(int v, int vl, int vr) {
if (lazy[v] == -1) return;
t[v] = lazy[v];
if (vl != vr) {
lazy[2 * v + 1] = lazy[2 * v + 2] = lazy[v];
}
lazy[v] = -1;
}
void update(int l, int r, int x, int v, int vl, int vr) {
propogate(v, vl, vr);
if (l > vr || vl > r) return;
else if (l <= vl && vr <= r) {
lazy[v] = x;
propogate(v, vl, vr);
} else {
int vm = (vl + vr) >> 1;
update(l, r, x, v << 1, vl, vm);
update(l, r, x, v << 1 | 1, vm + 1, vr);
t[v] = min(t[v << 1], t[v << 1 | 1]);
}
}
int query(int l, int r, int v, int vl, int vr) {
propogate(v, vl, vr);
if (l > vr || vl > r) return INT_MAX;
else if (l <= vl && vr <= r) return t[v];
else {
int vm = (vl + vr) >> 1;
int L = query(l, r, v << 1, vl, vm);
int R = query(l, r, v << 1 | 1, vm + 1, vr);
t[v] = min(t[v << 1], t[v << 1 | 1]);
return min(L, R);
}
}
void update(int l, int r, int x) {
update(l, r, x, 1, 0, n - 1);
}
int query(int l, int r) {
return query(l, r, 1, 0, n - 1);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < n; i++)
finalHeight[i] = 0;
if (n <= 10000 && k <= 5000) {
for (int i = 0; i < k; i++) {
for (int j = left[i]; j <= right[i]; j++) {
if (op[i] == 1) finalHeight[j] = max(finalHeight[j], height[i]);
else finalHeight[j] = min(finalHeight[j], height[i]);
}
}
} else {
int m = 0; while (op[m] == 1 && m < k) m++;
SegmentTreeMax mx(n);
SegmentTreeMin mn(n);
// #1
vector<pair<int, int>> q;
for (int i = 0; i < m; i++) {
q.push_back({height[i], i});
}
sort(q.begin(), q.end());
for (auto [noneed, i] : q) {
mx.update(left[i], right[i], height[i]);
}
//
for (int i = 0; i < n; i++) {
mn.update(i, i, mx.query(i, i));
}
// #2
while (!q.empty()) q.pop_back();
for (int i = m; i < k; i++) {
q.push_back({height[i], i});
}
sort(q.rbegin(), q.rend());
for (auto [noneed, i] : q) {
mn.update(left[i], right[i], height[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = mn.query(i, i);
}
}
return;
}
