#include "wall.h"
#include "bits/stdc++.h"
using namespace std;
const int inf = 1e9 + 1;
struct Node {
int L, R;
friend Node operator + (Node a, Node b) {
Node c;
c.L = max(a.L, b.L);
c.R = min(a.R, b.R);
if(c.L > c.R) {
if(c.L == a.L) c.L = c.R;
if(c.R == a.R) c.R = c.L;
}
return c;
}
};
vector<Node> ST;
void down(int id) {
Node x = ST[id];
ST[id * 2] = ST[id * 2] + x;
ST[id * 2 + 1] = ST[id * 2 + 1] + x;
ST[id] = {0, inf};
}
void update(int id, int l, int r, int u, int v, Node x) {
if(r < u || v < l) return ;
if(u <= l && r <= v) {
ST[id] = ST[id] + x;
return ;
}
down(id);
int mid = (l + r) / 2;
update(id * 2, l, mid, u, v, x);
update(id * 2 + 1, mid + 1, r, u, v, x);
}
Node get(int id, int l, int r, int x) {
if(l == r) return ST[id];
down(id);
int mid = (l + r) / 2;
if(x <= mid) {
return get(id * 2, l, mid, x);
} else {
return get(id * 2 + 1, mid + 1, r, x);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
ST.resize(4 * n + 4);
for(int i = 1; i <= 4 * n; i ++) ST[i] = {0, inf};
for(int i = 0; i < k; i ++) {
Node x = {0, inf};
if(op[i] == 1) x.L = height[i];
if(op[i] == 2) x.R = height[i];
update(1, 1, n, left[i] + 1, right[i] + 1, x);
}
for(int i = 0; i < n; i ++) {
finalHeight[i] = get(1, 1, n, i + 1).L;
}
}
