#include <bits/stdc++.h>
#include "wall.h"
#define ll long long
using namespace std;
const ll INF = 1e18;
struct segtree{
struct node{
ll mn, mx;
};
vector<node> tree;
ll size;
segtree(ll n){
size = 1;
while(size < n) size *= 2;
tree.resize(2 * size - 1, {0, INF});
}
void propagate(ll x, ll lx, ll rx){
tree[2 * x + 1].mn = min(tree[x].mx, max(tree[x].mn, tree[2 * x + 1].mn));
tree[2 * x + 1].mx = max(tree[x].mn, min(tree[x].mx, tree[2 * x + 1].mx));
tree[2 * x + 2].mn = min(tree[x].mx, max(tree[x].mn, tree[2 * x + 2].mn));
tree[2 * x + 2].mx = max(tree[x].mn, min(tree[x].mx, tree[2 * x + 2].mx));
tree[x].mn = 0;
tree[x].mx = INF;
}
void update(ll op, ll l, ll r, ll h, ll x, ll lx, ll rx){
if(r <= lx || rx <= l) return;
if(l <= lx && rx <= r){
if(op == 1){
tree[x].mn = max(tree[x].mn, h);
tree[x].mx = max(tree[x].mx, h);
}else{
tree[x].mn = min(tree[x].mn, h);
tree[x].mx = min(tree[x].mx, h);
}
return;
}
propagate(x, lx, rx);
ll mx = (lx + rx) / 2;
update(op, l, r, h, 2 * x + 1, lx, mx);
update(op, l, r, h, 2 * x + 2, mx, rx);
}
void update(ll op, ll l, ll r, ll h){
update(op, l, r, h, 0, 0, size);
}
ll query(ll pos, ll x, ll lx, ll rx){
if(rx - lx == 1){
return tree[x].mn;
}
propagate(x, lx, rx);
ll mx = (lx + rx) / 2;
if(pos < mx) return query(pos, 2 * x + 1, lx, mx);
return query(pos, 2 * x + 2, mx, rx);
}
ll query(ll pos){
return query(pos, 0, 0, size);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segtree st(n);
for (int i = 0; i < k; i++) st.update(op[i], left[i], right[i] + 1, height[i]);
for (int i = 0; i < n; i++) finalHeight[i] = st.query(i);
}
