#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
struct node {
int mn = 0, mx = inf;
};
struct SegTree {
vector<node> tree;
int n;
SegTree(int N) {
n = N;
while(__builtin_popcountll(n) != 1) ++n;
tree.resize(2 * n);
}
void prop(int v) {
tree[2 * v].mn = min(tree[v].mx, max(tree[v * 2].mn, tree[v].mn));
tree[2 * v].mx = max(tree[v].mn, min(tree[2 * v].mx, tree[v].mx));
tree[2 * v + 1].mn = min(tree[v].mx, max(tree[v * 2 + 1].mn, tree[v].mn));
tree[2 * v + 1].mx = max(tree[v].mn, min(tree[2 * v + 1].mx, tree[v].mx));
tree[v].mn = 0;
tree[v].mx = inf;
}
void update(int a, int b, int x, int y, int k, int v, int op) {
if(a > y || b < x) return;
if(a <= x && y <= b) {
if(op == 1) {
tree[k].mx = max(tree[k].mx, v);
tree[k].mn = max(tree[k].mn, v);
} else {
tree[k].mx = min(tree[k].mx, v);
tree[k].mn = min(tree[k].mn, v);
}
return;
}
prop(k);
int d = (x + y) / 2;
update(a, b, x, d, 2 * k, v, op);
update(a, b, d + 1, y, 2 * k + 1, v, op);
}
void update(int a, int b, int v, int op) {
update(a, b, 0, n - 1, 1, v, op);
}
int get(int x, int y, int k, int p) {
if(x == y)
return tree[k].mn;
prop(k);
int d = (x + y) / 2;
if(p <= d)
return get(x, d, 2 * k, p);
return get(d + 1, y, 2 * k + 1, p);
}
int get(int p) {
return get(0, n - 1, 1, p);
}
void print() {
for(int i = 0; i < 2 * n; ++i) {
cout << i << ' ' << tree[i].mn << ' ' << tree[i].mx << "\n";
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegTree sgt(n);
for(int i = 0; i < k; ++i) {
sgt.update(left[i], right[i], height[i], op[i]);
}
for(int i = 0; i < n; ++i) {
finalHeight[i] = sgt.get(i);
}
}
