#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int mn = 0, mx = 0;
node operator+(node other) {
return {min(mn, other.mn), max(mx, other.mx)};
}
};
vector<node> seg, lazy;
int N;
const int INF = 1e9;
void apply(int idx, node val) {
seg[idx].mn = max(seg[idx].mn, val.mn);
seg[idx].mx = max(seg[idx].mx, val.mn);
seg[idx].mn = min(seg[idx].mn, val.mx);
seg[idx].mx = min(seg[idx].mx, val.mx);
lazy[idx].mn = max(lazy[idx].mn, val.mn);
lazy[idx].mx = max(lazy[idx].mx, val.mn);
lazy[idx].mn = min(lazy[idx].mn, val.mx);
lazy[idx].mx = min(lazy[idx].mx, val.mx);
}
void push_down(int idx) {
apply(idx * 2, lazy[idx]);
apply(idx * 2 + 1, lazy[idx]);
lazy[idx] = {0, INF};
}
void range_update(int ul, int ur, node &uval, int idx = 1, int l = 0, int r = N - 1) {
if(ul <= l && r <= ur) {
apply(idx, uval);
return;
}
push_down(idx);
int m = l + (r - l) / 2;
if(ul <= m) range_update(ul, ur, uval, idx * 2, l, m);
if(ur >= m + 1) range_update(ul, ur, uval, idx * 2 + 1, m + 1, r);
seg[idx] = seg[idx * 2] + seg[idx * 2 + 1];
}
node query_at(int ql, int qr, int idx = 1, int l = 0, int r = N - 1) {
if(ql <= l && r <= qr) return seg[idx];
push_down(idx);
int m = l + (r - l) / 2;
node res = {INF, 0};
if(ql <= m) res = res + query_at(ql, qr, idx * 2, l, m);
if(qr >= m + 1) res = res + query_at(ql, qr, idx * 2 + 1, m + 1, r);
return res;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
seg.resize(n * 4); lazy.assign(n * 4, {0, INF});
N = n;
for(int i = 0; i < k; ++i) {
node q = {0, INF};
if(op[i] == 1) {
q.mn = height[i];
} else {
q.mx = height[i];
}
range_update(left[i], right[i], q);
}
for(int i = 0; i < n; ++i) {
finalHeight[i] = query_at(i, i).mx;
}
}
