#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pr = pair<int, int>;
const int INF = 1e9+7, MOD = 1e9+7;
vector<int> a;
struct segtree{
vector<int> st, up, down;
int n;
void init(int N) {
n = N;
st.assign(4*n, 0);
down.assign(4*n, -1);
up.assign(4*n, -1);
}
int L(int i) {return i << 1;}
int R(int i) {return i << 1 | 1;}
void push(int i, int l, int r) {
if (up[i] == -1 && down[i] == -1) return;
if (up[i] != -1) {
if (l == r) {
st[i] = max(up[i], st[i]);
}
else {
up[L(i)] = up[i];
up[R(i)] = up[i];
}
}
if (down[i] != -1) {
if (l == r) {
st[i] = min(st[i], down[i]);
}
else {
down[L(i)] = down[i];
down[R(i)] = down[i];
}
}
down[i] = -1;
up[i] = -1;
}
void update(int i, int l, int r, int ll, int rr, int op, int h) {
push(i, l, r);
if (r < ll || l > rr) return;
if (ll <= l && r <= rr) {
if (op == 1) up[i] = h;
else down[i] = h;
return;
}
int m = (l + r) >> 1;
update(L(i), l, m, ll, rr, op, h);
update(R(i), m+1, r, ll, rr, op, h);
}
void query(int i, int l, int r) {
push(i, l, r);
if (l == r) {
a[l] = st[i];
return;
}
int m = (l + r) >> 1;
query(L(i), l, m);
query(R(i), m + 1, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
segtree seg;
a.resize(n+1);
seg.init(n);
for (int i = 0; i < k; i++) {
seg.update(1, 1, n, left[i]+1, right[i]+1, op[i], height[i]);
// seg.query(1, 1, n);
// for (int j = 0; j < n; j++) {
// finalHeight[j] = a[j+1];
// }
// for (int j = 1; j <= n; j++)
// cout << j << ' ' << a[j] << '\n';
}
seg.query(1, 1, n);
for (int i = 0; i < n; i++) {
finalHeight[i] = a[i+1];
}
return;
}
