#include <wall.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
struct node{
int mx = INT_MAX, mn = 0;
int val = 0;
};
vector<node> st;
int len = 1;
void prop(int i){
node& n = st[i], &l = st[i * 2], &r = st[i * 2 + 1];
smin(l.mx, n.mx); smax(l.mx, n.mn);
smax(l.mn, n.mn); smin(l.mn, n.mx);
smin(l.val, n.mx); smax(l.val, n.mn);
smin(r.mx, n.mx); smax(r.mx, n.mn);
smax(r.mn, n.mn); smin(r.mn, n.mx);
smin(r.val, n.mx); smax(r.val, n.mn);
n.mx = INT_MAX;
n.mn = 0;
}
void upd(int l, int r, int mx, int mn, int i = 1, int s = 0, int e = len){
if(e <= l || s >= r) return;
if(l <= s && e <= r){
smin(st[i].mx, mx); smax(st[i].mx, mn);
smax(st[i].mn, mn); smin(st[i].mn, mx);
smin(st[i].val, mx); smax(st[i].val, mn);
return;
}
prop(i);
upd(l, r, mx, mn, i * 2, s, (s + e) / 2);
upd(l, r, mx, mn, i * 2 + 1, (s + e) / 2, e);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
while(len < n) len *= 2;
st.resize(2 * len);
for (int i = 0; i < k; i++) {
int mx = INT_MAX, mn = 0;
if(op[i] == 1) mn = height[i];
else mx = height[i];
upd(left[i], right[i] + 1, mx, mn);
}
for (int i = 1; i < len; i++) {
prop(i);
}
for (int i = len; i < len + n; i++) {
finalHeight[i - len] = st[i].val;
}
return;
}
