#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
struct Segment {
struct Node {
int mn = 0;
int mx = INF;
Node() : mn(0), mx(INF) {}
void add(int h) {
mn = max(mn, h);
mx = max(mx, mn);
}
void remove(int h) {
mx = min(mx, h);
mn = min(mn, mx);
}
};
int n;
vector<Node> t;
Segment(int _n) {
for (n = 1; n < _n; n *= 2)
;
t.resize(2 * n);
}
void prop(int i) {
t[2 * i].add(t[i].mn);
t[2 * i].remove(t[i].mx);
t[2 * i + 1].add(t[i].mn);
t[2 * i + 1].remove(t[i].mx);
t[i] = Node();
}
void update(int i, int a, int b, int l, int r, int h, bool flag) {
if (b <= l || r <= a)
return;
if (l <= a && b <= r) {
if (flag)
t[i].add(h);
else
t[i].remove(h);
return;
}
prop(i);
int m = (a + b) / 2;
update(2 * i, a, m, l, r, h, flag);
update(2 * i + 1, m, b, l, r, h, flag);
}
void update(int l, int r, int h, bool flag = true) {
update(1, 0, n, l, r, h, flag);
}
int query(int p) {
int ans = 0;
for (p += n; p > 0; p >>= 1) {
ans = max(ans, t[p].mn);
ans = min(ans, t[p].mx);
}
return ans;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segment T(n);
for (int i = 0; i < k; i++) {
T.update(left[i], right[i] + 1, height[i], (op[i] == 1));
}
for (int i = 0; i < n; i++) {
finalHeight[i] = T.query(i);
}
return;
}
