#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second
template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;
typedef long long ll;
typedef double db;
const int mod = 1e9 + 7;
vv<pp<int, int>> st, lv;
void push(int node) {
if (lv[node].fst != -1) {
int u = node * 2;
if (st[u].snd < lv[node].fst) st[u].fst = st[u].snd = lv[u].fst = lv[u].snd = lv[node].fst;
else st[u].fst = lv[u].fst = max(st[u].fst, lv[node].fst);
u++;
if (st[u].snd < lv[node].fst) st[u].fst = st[u].snd = lv[u].fst = lv[u].snd = lv[node].fst;
else st[u].fst = lv[u].fst = max(st[u].fst, lv[node].fst);
}
if (lv[node].snd != -1) {
int u = node * 2;
if (st[u].fst > lv[node].snd) st[u].fst = st[u].snd = lv[u].fst = lv[u].snd = lv[node].snd;
else st[u].snd = lv[u].snd = max(st[u].snd, lv[node].snd);
u++;
if (st[u].fst > lv[node].snd) st[u].fst = st[u].snd = lv[u].fst = lv[u].snd = lv[node].snd;
else st[u].snd = lv[u].snd = max(st[u].snd, lv[node].snd);
}
lv[node] = {-1, -1};
}
void upd(int x, int y, int l, int r, int node, int tp, int val) {
if (x > r || y < l) return;
if (x <= l && y >= r) {
if (tp == 1) {
st[node].fst = max(st[node].fst, val);
st[node].snd = max(st[node].snd, val);
lv[node] = st[node];
}
else {
st[node].snd = min(st[node].snd, val);
st[node].fst = min(st[node].fst, val);
lv[node] = st[node];
}
return;
}
int m = (l + r) / 2;
push(node);
st[node] = {0, INT_MAX};
upd(x, y, l, m, node * 2, tp, val);
upd(x, y, m + 1, r, node * 2 + 1, tp, val);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
int s = 1;
while (s < n) s <<= 1;
st.assign(s << 1, {0, INT_MAX});
lv.assign(s << 1, {-1, -1});
for (int i = 0; i < k; i++) upd(left[i], right[i], 0, s - 1, 1, op[i], height[i]);
for (int i = 1; i < s; i++) push(i);
for (int i = 0; i < n; i++) finalHeight[i] = st[i + s].fst;
}
