#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
vll h;
ll n;
struct Seg {
vll seg;
ll sz = 1;
vpll set_val;
Seg() {
for (; sz < n; sz *= 2);
seg.resize(2*sz);
set_val.resize(2*sz, {0, inf});
}
void push(ll node) {
if (node >= sz) return;
ll low = set_val[node].first;
ll high = set_val[node].second;
ll child = node * 2;
set_val[child].first = max(set_val[child].first, low);
set_val[child].second = min(set_val[child].second, high);
child = node * 2 + 1;
set_val[child].first = max(set_val[child].first, low);
set_val[child].second = min(set_val[child].second, high);
set_val[node].first = 0;
set_val[node].second = inf;
}
void update(ll l, ll r, ll tl, ll tr, ll i, ll type, ll val) {
if (tl > r || tr < l) return;
push(i);
if (tl >= l && tr <= r) {
if (type == 1) {
set_val[i].first = max(set_val[i].first, val);
} else {
set_val[i].second = min(set_val[i].second, val);
}
push(i);
return;
}
ll mid = (tl + tr) / 2;
update(l, r, tl, mid, i*2, type, val);
update(l, r, mid+1, tr, i*2+1, type, val);
}
ll query(ll i, ll l, ll r, ll idx) {
push(i);
if (l == r) {
return min(set_val[i].first, set_val[i].second);
}
ll mid = (l + r) / 2;
if (idx <= mid) {
return query(i*2, l, mid, idx);
} else {
return query(i*2+1, mid+1, r, idx);
}
}
};
void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
n = N;
Seg seg;
loop(i,0,k) {
ll l = left[i];
ll r = right[i];
ll hi = height[i];
if (op[i] == 1) {
seg.update(l, r, 0, n-1, 1, 1, hi);
} else {
seg.update(l, r, 0, n-1, 1, 2, hi);
}
}
loop(i,0,n) {
finalHeight[i] = seg.query(1, 0, n-1, i);
}
}
