#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
constexpr int N = 2e6;
int mn[N * 4], mx[N * 4];
bool has[N * 4];
void push(int id, int tl, int tr) {
if (!has[id] || tl == tr) return;
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
has[x] = has[y] = 1;
mx[x] = mx[y] = mx[id];
mn[x] = mn[y] = mn[id];
has[id] = 0;
}
void add(int id, int tl, int tr, int l, int r, int h) {
push(id, tl, tr);
if (r < tl || tr < l || mn[id] >= h) return;
if (l <= tl && tr <= r && mx[id] <= h) {
has[id] = 1;
mn[id] = mx[id] = max(h, mx[id]);
push(id, tl, tr);
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
add(x, tl, tm, l, r, h);
add(y, tm + 1, tr, l, r, h);
mn[id] = min(mn[x], mn[y]);
mx[id] = max(mx[x], mx[y]);
}
void remove(int id, int tl, int tr, int l, int r, int h) {
push(id, tl, tr);
if (r < tl || tr < l || mx[id] <= h) return;
if (l <= tl && tr <= r && mn[id] >= h) {
has[id] = 1;
mn[id] = mx[id] = min(h, mn[id]);
push(id, tl, tr);
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
remove(x, tl, tm, l, r, h);
remove(y, tm + 1, tr, l, r, h);
mn[id] = min(mn[x], mn[y]);
mx[id] = max(mx[x], mx[y]);
}
int get(int id, int tl, int tr, int i) {
push(id, tl, tr);
if (tl == tr) {
return mx[id];
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm) {
return get(x, tl, tm, i);
} else {
return get(y, tm + 1, tr, i);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < k; i++) {
int t = op[i], l = left[i], r = right[i], h = height[i];
if (t == 1) {
add(0, 0, n - 1, l, r, h);
} else {
remove(0, 0, n - 1, l, r, h);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = get(0, 0, n - 1, i);
}
}
