#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = (1 << 22);
int low[MAX], high[MAX];
void pushHigh(int v, int pa) {
high[v] = min(high[v], high[pa]);
low[v] = min(low[v], high[v]);
}
void relaxHigh(int v, int l, int r) {
if (l != r) {
pushHigh(v << 1, v);
pushHigh((v << 1) | 1, v);
}
high[v] = MAX;
}
void pushLow(int v, int pa) {
low[v] = max(low[v], low[pa]);
high[v] = max(high[v], low[v]);
}
void relaxLow(int v, int l, int r) {
if (l != r) {
pushLow(v << 1, v);
pushLow((v << 1) | 1, v);
}
low[v] = 0;
}
void relax(int v, int l, int r) {
if (l != r) {
if (high[v] != MAX) relaxHigh(v, l, r);
if (low[v] != 0) relaxLow(v, l, r);
}
}
void upd(int v, int l, int r, int ul, int ur, int h, int type) {
if (r < ul || ur < l) return;
relax(v, l, r);
if (ul <= l && r <= ur) {
(type == 1 ? (low[v] = h, high[v] = max(low[v], high[v])) : (high[v] = h, low[v] = min(low[v], high[v])));
relax(v, l, r);
}
else {
int mid = (l + r) >> 1;
upd(v << 1, l, mid, ul, ur, h, type);
upd((v << 1) | 1, mid + 1, r, ul, ur, h, type);
}
}
void getAll(int v, int l, int r, int finalHeight[]) {
if (l == r) finalHeight[l] = low[v];
else {
relax(v, l, r);
int mid = (l + r) >> 1;
getAll(v << 1, l, mid, finalHeight);
getAll((v << 1) | 1, mid + 1, r, finalHeight);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int i = 0; i < MAX; ++i) {
high[i] = MAX;
}
for (int i = 0; i < k; ++i) {
upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
}
getAll(1, 0, n - 1, finalHeight);
}
