#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int arr[2000069];
void merge(pair<int, int> &x, pair<int, int> y) {
if (y.s < x.f) x = {y.s, y.s};
else if (y.f > x.s) x = {y.f, y.f};
else x = {max(x.f, y.f), min(x.s, y.s)};
}
struct node {
int l, r;
node *lft, *rht;
pair<int, int> val;
node(int tl, int tr): l(tl), r(tr), val({0, INT_MAX}) {
if (l + 1 == r) {
lft = rht = NULL;
return;
}
lft = new node(l, (l + r) / 2);
rht = new node((l + r) / 2, r);
}
void clean() {
if (l + 1 == r) return;
merge(lft->val, val);
merge(rht->val, val);
val = {0, INT_MAX};
}
void upd(int tl, int tr, pair<int,int> nw) {
if (tr <= l || r <= tl) return;
if (tl <= l && r <= tr) {
merge(val, nw);
return;
}
clean();
lft->upd(tl, tr, nw);
rht->upd(tl, tr, nw);
}
void outp() {
if (l + 1 == r) {
arr[l] = val.f;
return;
}
clean();
lft->outp();
rht->outp();
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0, n);
for (int i = 0; i < k; i++) {
pair<int,int> tmp = {0, INT_MAX};
if (op[i] == 1) tmp.f = height[i];
else tmp.s = height[i];
root->upd(left[i], right[i] + 1, tmp);
}
root->outp();
for (int i = 0; i < n; i++) {
finalHeight[i] = arr[i];
}
}
