#include <iostream>
#include <vector>
#include "wall.h"
using namespace std;
int const INF = 1e5;
struct Node {
int minn;
int maxx;
};
Node combineNode(Node a, Node b) {
Node c;
c.minn = min(b.maxx, max(a.minn, b.minn));
c.maxx = max(b.minn, min(a.maxx, b.maxx));
return c;
}
struct SegmentTree {
vector <Node> seg;
SegmentTree(int n) {
seg.resize(1 + 4 * n);
for(int i = 1;i <= 4 * n;i++) {
seg[i] = {0, INF};
}
}
void cleanNode(int node, int from, int to) {
if(from != to) {
seg[node * 2] = combineNode(seg[node * 2], seg[node]);
seg[node * 2 + 1] = combineNode(seg[node * 2 + 1], seg[node]);
seg[node] = {0, INF};
}
}
void update(int node, int from, int to, int x, int y, Node add) {
if(from == x && to == y) {
seg[node] = combineNode(seg[node], add);
cleanNode(node, from, to);
} else {
int mid = (from + to) / 2;
cleanNode(node * 2, from, mid);
cleanNode(node * 2 + 1, mid+1, to);
if(y <= mid) {
update(node * 2, from, mid, x, y, add);
} else if(mid < x) {
update(node * 2 + 1, mid+1, to, x, y, add);
} else {
update(node * 2, from, mid, x, mid, add);
update(node * 2 + 1, mid+1, to, mid+1, y, add);
}
}
}
Node query(int node, int from, int to, int x) {
cleanNode(node, from, to);
if(from == to) {
return seg[node];
} else {
int mid = (from + to) / 2;
if(x <= mid) {
return query(node*2, from, mid, x);
} else {
return query(node*2+1, mid+1, to, x);
}
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
SegmentTree seg(n);
seg.update(1, 1, n, 1, n, {0, 0});
for(int i = 0;i < k;i++) {
int x = left[i]+1, y = right[i]+1;
Node add;
if(op[i] == 1) {
add = {height[i], INF};
} else {
add = {0, height[i]};
}
seg.update(1, 1, n, x, y, add);
}
for(int i = 0;i < n;i++) {
finalHeight[i] = seg.query(1, 1, n, i+1).minn;
}
return;
}
