#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class segment_tree {
private:
struct node {
T min, max;
};
int n;
vector<node> t;
void push(int v, int vl, int vr) {
if (vl == vr) return;
t[2 * v + 1].min = ::max(t[v].min, ::min(t[2 * v + 1].min, t[v].max));
t[2 * v + 1].max = ::min(t[v].max, ::max(t[2 * v + 1].max, t[v].min));
t[2 * v + 2].min = ::max(t[v].min, ::min(t[2 * v + 2].min, t[v].max));
t[2 * v + 2].max = ::min(t[v].max, ::max(t[2 * v + 2].max, t[v].min));
t[v].min = 0; t[v].max = LLONG_MAX;
}
T get(int i, int v, int vl, int vr) {
push(v, vl, vr);
if (vl == vr) {
return t[v].min;
} else {
int vm = (vl + vr) / 2;
if (i <= vm)
return get(i, 2 * v + 1, vl, vm);
else
return get(i, 2 * v + 2, vm + 1, vr);
}
}
void update(int l, int r, T x, int v, int vl, int vr, int type) {
push(v, vl, vr);
if (l > vr || vl > r)
return;
if (l <= vl && vr <= r) {
if (type == 1) {
t[v].min = ::max(t[v].min, x);
t[v].max = ::max(t[v].max, x);
} else {
t[v].min = ::min(t[v].min, x);
t[v].max = ::min(t[v].max, x);
}
} else {
int vm = (vl + vr) / 2;
update(l, r, x, 2 * v + 1, vl, vm, type);
update(l, r, x, 2 * v + 2, vm + 1, vr, type);
}
}
public:
segment_tree(int k) {
n = 1; while (n < k) n <<= 1;
t = vector<node> (2 * n - 1, {0, LLONG_MAX});
}
T get(int i) {
return get(i, 0, 0, n - 1);
}
void update(int l, int r, T x, int type) {
update(l, r, x, 0, 0, n - 1, type);
}
};
void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
segment_tree<long long> st(n);
for (int i = 0; i < k; i++) {
st.update(l[i], r[i], h[i], op[i]);
}
for (int i = 0; i < n; i++) {
ans[i] = st.get(i);
}
return;
}
