#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = (1 << 30) - 1;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
struct Segtree {
int n;
vector<P> dat;
P ei = P(INF, -INF);
Segtree(int n_) {
n = 1;
while (n < n_) {
n <<= 1;
}
dat.resize(2 * n, ei);
}
inline void merge(P &p1, P p2) {
chmin(p1.first, p2.first);
chmin(p1.second, p2.first);
chmax(p1.second, p2.second);
}
inline void eval(int k) {
if (k < n) {
merge(dat[k << 1], dat[k]);
merge(dat[k << 1 | 1], dat[k]);
dat[k] = ei;
}
}
void upd(int a, int b, P x, int k, int l, int r) {
eval(k);
if (b <= l || r <= a) {
return;
}
if (a <= l && r <= b) {
merge(dat[k], x);
eval(k);
return;
}
upd(a, b, x, k << 1, l, (l + r) >> 1);
upd(a, b, x, k << 1 | 1, (l + r) >> 1, r);
}
inline void upd(int a, int b, P x) { return upd(a, b, x, 1, 0, n); }
int get(int k, int x) {
k += n;
P p = dat[k];
k >>= 1;
while (k > 0) {
merge(p, dat[k]);
k >>= 1;
}
chmin(x, p.first);
chmax(x, p.second);
return x;
}
void out() {
for (int i = 0; i < 2 * n; i++) {
cout << i << " " << dat[i].first << " " << dat[i].second << endl;
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
Segtree seg(n);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
seg.upd(left[i], right[i] + 1, P(INF, height[i]));
} else {
seg.upd(left[i], right[i] + 1, P(height[i], -INF));
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = seg.get(i, 0);
}
}
