#include "wall.h"
#include <algorithm>
using namespace std;
const int MAXN = 2000000;
const int INFINIT = 100000;
int answer[MAXN];
struct SegmentTree {
struct Node {
int lazymin, lazymax;
} tree[4 * MAXN];
int n;
void build(int node, int left, int right) {
tree[node] = {INFINIT, 0};
if(left < right) {
int middle = (left + right) / 2;
build(2 * node, left, middle);
build(2 * node + 1, middle + 1, right);
}
}
void init(int n) {
this->n = n;
build(1, 0, n - 1);
}
void addLazy(int node, int type, int val) {
if(type == 1) {
tree[node].lazymin = max(tree[node].lazymin, val);
tree[node].lazymax = max(tree[node].lazymax, val);
} else {
tree[node].lazymin = min(tree[node].lazymin, val);
tree[node].lazymax = min(tree[node].lazymax, val);
}
}
void propagate(int node) {
addLazy(2 * node, 1, tree[node].lazymax);
addLazy(2 * node, 2, tree[node].lazymin);
addLazy(2 * node + 1, 1, tree[node].lazymax);
addLazy(2 * node + 1, 2, tree[node].lazymin);
tree[node].lazymax = 0;
tree[node].lazymin = INFINIT;
}
void update(int node, int left, int right, int qleft, int qright, int type, int val) {
if(qleft <= left && right <= qright) {
addLazy(node, type, val);
} else {
propagate(node);
int middle = (left + right) / 2;
if(qleft <= middle) {
update(2 * node, left, middle, qleft, qright, type, val);
}
if(middle < qright) {
update(2 * node + 1, middle + 1, right, qleft, qright, type, val);
}
}
}
void update(int st, int dr, int type, int val) {
update(1, 0, n - 1, st, dr, type, val);
}
void dfs(int node, int left, int right) {
if(left == right) {
answer[left] = tree[node].lazymax;
} else {
propagate(node);
int middle = (left + right) / 2;
dfs(2 * node, left, middle);
dfs(2 * node + 1, middle + 1, right);
}
}
void dfs() {
dfs(1, 0, n - 1);
}
} aint;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
aint.init(n);
for(int i = 0; i < k; i++) {
aint.update(left[i], right[i], op[i], height[i]);
}
aint.dfs();
for(int i = 0; i < n; i++) {
finalHeight[i] = answer[i];
}
}
