#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
int res[2000005];
struct node {
node *left, *right;
int S, E, lo, hi;
node(int _s, int _e) : S(_s), E(_e), lo(0), hi(100000) {
if (S == E) return;
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
}
void s_upd(int v, int ty) {
if (ty == 1) {
if (v > hi) lo = hi = v;
else lo = max(lo, v);
} else {
if (v < lo) lo = hi = v;
else hi = min(hi, v);
}
}
void prop() {
if (S == E) return;
left->s_upd(lo, 1);
left->s_upd(hi, 2);
right->s_upd(lo, 1);
right->s_upd(hi, 2);
lo = 0;
hi = 100000;
}
void upd(int l, int r, int v, int ty) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
s_upd(v, ty);
return;
}
prop();
left->upd(l, r, v, ty);
right->upd(l, r, v, ty);
}
void trav() {
if (S == E) {
res[S] = lo;
return;
}
prop();
left->trav();
right->trav();
}
} *root;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
root = new node(0, n - 1);
for (int i = 0; i < k; i++)
root->upd(left[i], right[i], height[i], op[i]);
root->trav();
for (int i = 0; i < n; i++) finalHeight[i] = res[i];
}
