#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF = 1e9;
struct node {
int val, lb, ub;
int st, en;
node *left, *right;
void lazy() {
left->val = max(left->val, lb);
left->lb = max(left->lb, lb);
left->ub = max(left->ub, lb);
left->val = min(left->val, ub);
left->lb = min(left->lb, ub);
left->ub = min(left->ub, ub);
right->val = max(right->val, lb);
right->lb = max(right->lb, lb);
right->ub = max(right->ub, lb);
right->val = min(right->val, ub);
right->lb = min(right->lb, ub);
right->ub = min(right->ub, ub);
lb = -INF;
ub = INF;
}
void build(int start, int end) {
st = start;
en = end;
lb = -INF;
ub = INF;
if (st == en) {
val = lb = ub = 0;
return;
}
int md = (st + en)/2;
left = new node();
right = new node();
left->build(st, md);
right->build(md + 1, en);
}
int query(int id) {
if (st > id || en < id) return 0;
if (st == en) return val;
lazy();
return left->query(id) + right->query(id);
}
void updatebounds(int lf, int rg, int x, int y) {
if (st > rg || en < lf) return;
if (lf <= st && en <= rg) {
val = max(val, x);
lb = max(lb, x);
ub = max(ub, x);
val = min(val, y);
lb = min(lb, y);
ub = min(ub, y);
return;
}
lazy();
left->updatebounds(lf, rg, x, y);
right->updatebounds(lf, rg, x, y);
}
} sg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
sg.build(0, n - 1);
for (int i = 0; i < k; i++) {
if (op[i] == 1) {
sg.updatebounds(left[i], right[i], height[i], INF);
} else if (op[i] == 2) {
sg.updatebounds(left[i], right[i], -INF, height[i]);
}
}
for (int i = 0; i < n; i++) {
finalHeight[i] = sg.query(i);
}
return;
}
