#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, 1e9 + 1);
up.assign(4*n, -1);
}
int L(int i) {return i << 1;}
int R(int i) {return i << 1 | 1;}
void merge(int i, int op, int h) {
if (op == 1) {
if (up[i] < h) {
up[i] = h;
down[i] = max(down[i], h);
}
} else {
if (down[i] > h) {
down[i] = h;
up[i] = min(up[i], h);
}
}
}
void push(int i, int l, int r) {
if (up[i] == -1 && down[i] == 1e9 + 1) return;
if (up[i] != -1) {
merge(L(i), 1, up[i]);
merge(R(i), 1, up[i]);
}
if (down[i] != 1e9 + 1) {
merge(L(i), 2, down[i]);
merge(R(i), 2, down[i]);
}
down[i] = 1e9 + 1;
up[i] = -1;
}
void update(int i, int l, int r, int ll, int rr, int op, int h) {
if (ll == l && r == rr) {
merge(i, op, h);
return;
}
push(i, l, r);
int m = (l + r) >> 1;
if (rr <= m) update(L(i), l, m, ll, rr, op, h);
else if (m + 1 <= ll) update(R(i), m+1, r, ll, rr, op, h);
else {
update(L(i), l, m, ll, m, op, h);
update(R(i), m+1, r, m + 1, rr, op, h);
}
}
void query(int i, int l, int r) {
if (l == r) {
a[l] = down[i];
return;
}
push(i, l, r);
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);
seg.update(1, 1, n, 1, n, 1, 0);
seg.update(1, 1, n, 1, n, 2, 0);
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;
}
