#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, l, r) for(int i = l; i <= r; i++)
#define FORD(i, l, r) for(int i = l; i >= r; i--)
#define db double
#define ldb long double
#define all_1(x) (x).begin() + 1, (x).end()
#define all(x) (x).begin(), (x).end()
#define ins insert
#define pb push_back
template<typename T>
void debug_var(const T &var, const string &name) {
cerr << name << ": " << var << "\n";
}
template<typename T>
void debug_1d(const T &vt, const string &name) {
if (vt.empty()) {
cerr << name << " is empty!\n";
return;
}
FOR(i, 0, (int)vt.size() - 1) {
cerr << name << "[" << i << "]: " << vt[i] << "\n";
}
}
struct node {
int maxi, mini;
node() {
maxi = 0;
mini = 2e9;
}
};
struct segment_tree {
int _n;
vector<node> _st;
segment_tree(int n = 0) {
init(n);
}
void init(int n) {
_n = n;
_st.assign(4 * _n + 5, node());
}
void apply(int i, int low, int high) {
_st[i].mini = max(_st[i].mini, low);
_st[i].maxi = max(_st[i].maxi, low);
_st[i].maxi = min(_st[i].maxi, high);
_st[i].mini = min(_st[i].mini, high);
}
void down(int i) {
int cl = (i << 1), cr = (cl | 1);
apply(cl, _st[i].mini, _st[i].maxi);
apply(cr, _st[i].mini, _st[i].maxi);
}
void update_chmax(int i, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
//add bricks
if (l >= u && r <= v) {
_st[i].maxi = max(_st[i].maxi, val);
_st[i].mini = max(_st[i].mini, val);
return;
}
down(i);
int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
update_chmax(cl, l, m, u, v, val);
update_chmax(cr, m + 1, r, u, v, val);
_st[i].mini = min(_st[cl].mini, _st[cr].mini);
_st[i].maxi = max(_st[cl].maxi, _st[cr].maxi);
}
void update_chmin(int i, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
//add bricks
if (l >= u && r <= v) {
_st[i].maxi = min(_st[i].maxi, val);
_st[i].mini = min(_st[i].mini, val);
return;
}
down(i);
int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
update_chmin(cl, l, m, u, v, val);
update_chmin(cr, m + 1, r, u, v, val);
_st[i].mini = min(_st[cl].mini, _st[cr].mini);
_st[i].maxi = max(_st[cl].maxi, _st[cr].maxi);
}
void build_ans(int i, int l, int r, int *res) {
if (l == r) {
res[l - 1] = min(_st[i].maxi, _st[i].mini);
return;
}
int m = (l + r) >> 1, cl = (i << 1), cr = (cl | 1);
down(i);
build_ans(cl, l, m, res);
build_ans(cr, m + 1, r, res);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segment_tree st(n + 5);
FOR(i, 0, k - 1) {
if (op[i] == 1) st.update_chmax(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
else st.update_chmin(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
}
st.build_ans(1, 1, n, finalHeight);
}
