//#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ff first
#define ss second
vector <int> lz, sum;
vector <bool> has;
vector <int> lo, hi;
void propagate(int id) {
int x = id * 2 + 1;
int y = x + 1;
lo[x] = max(lo[x], lo[id]);
hi[x] = max(hi[x], lo[id]);
lo[x] = min(lo[x], hi[id]);
hi[x] = min(hi[x], hi[id]);
lo[y] = max(lo[y], lo[id]);
hi[y] = max(hi[y], lo[id]);
lo[y] = min(lo[y], hi[id]);
hi[y] = min(hi[y], hi[id]);
lo[id] = -1;
hi[id] = INT_MAX;
}
int query(int id, int l, int r, int i, int val) {
int cur = max(val, lo[id]);
cur = min(cur, hi[id]);
if (l == r)
return cur;
propagate(id);
int mid = (l + r) / 2, x = id * 2 + 1, y = x + 1, a;
if (i <= mid)
return query(x, l, mid, i, cur);
else
return query(y, mid + 1, r, i, cur);
}
void update(int id, int l, int r, int L, int R, int k, int op) {
if (L <= l && r <= R) {
if (op == 1)
lo[id] = max(lo[id], k);
else
hi[id] = min(hi[id], k);
return;
}
propagate(id);
int m = (l + r) / 2;
if (R <= m) {
update(id * 2 + 1, l, m, L, R, k, op);
}
else if (L > m) {
update(id * 2 + 2, m + 1, r, L, R, k, op);
}
else {
update(id * 2 + 1, l, m, L, m, k, op);
update(id * 2 + 2, m + 1, r, m + 1, R, k, op);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
lz.resize(4 * n, 0);
has.resize(4 * n, 0);
lo.assign(4 * n, 0);
hi.assign(4 * n, INT_MAX);
for (int i = 0;i < k;i++) {
if (op[i] == 1) {
update(0, 0, n - 1, left[i], right[i], height[i], 1);
}
else {
update(0, 0, n - 1, left[i], right[i], height[i], 2);
}
}
for (int i = 0;i < n;i++) {
finalHeight[i] = query(0, 0, n - 1, i, 0);
}
// for (int i = 0;i < n;i++) {
// cout << finalHeight[i] << " ";
// }
// cout << endl;
}
