#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define F first
#define S second
#define lc 2 * p
#define rc 2 * p + 1
constexpr int logn = 21;
constexpr int maxn = (1 << logn);
constexpr ll infty = LLONG_MAX;
pll seg[maxn * 2];
// t1 is old trim; t2 is new trim
pll combine(pll t1, pll t2) {
if (t1.F > t2.S) return make_pair(t2.S, t2.S);
if (t2.F > t1.S) return make_pair(t2.F, t2.F);
return make_pair(max(t1.F, t2.F), min(t1.S, t2.S));
}
void pushdn(int p) {
seg[lc] = combine(seg[lc], seg[p]);
seg[rc] = combine(seg[rc], seg[p]);
seg[p] = make_pair(0, infty); // makes p irrelevant
}
void rangeupdate(int p, int l, int r, int a, int b, pll val) {
if (a > r || b < l) return;
if (a <= l && r <= b) {
seg[p] = combine(seg[p], val);
return;
}
pushdn(p);
int mid = (l + r) / 2;
rangeupdate(lc, l, mid, a, b, val);
rangeupdate(rc, mid + 1, r, a, b, val);
}
pll walkseg(int p, int l, int r, int idx) {
if (l == r) {
assert(idx == l);
return seg[p];
}
int mid = (l + r) / 2;
if (idx <= mid) {
return combine(walkseg(lc, l, mid, idx), seg[p]);
} else {
return combine(walkseg(rc, mid + 1, r, idx), seg[p]);
}
}
ll compute(pll trim, ll val) {
if (val < trim.F) return trim.F;
if (val < trim.S) return trim.S;
return val;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
// cout << n << ' ' << k << '\n';
for (int i = 0; i < k; i++) {
// cout << "query " << op[i] << ' ' << left[i] << ' ' << right[i] << ' ' << height[i] << '\n';
if (op[i] == 1) {
rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(height[i], infty));
} else {
rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(0, height[i]));
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = compute(walkseg(1, 0, maxn - 1, i), 0);
}
return;
}
