/***********************************************
* auth: tapilyoca *
* date: 04/15/2025 at 08:29:42 *
* dots: https://github.com/tapilyoca/dotilyoca *
***********************************************/
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long long MOD = 1e9+7;
template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;
/***********************************************/
struct Segtree {
int l, r;
Segtree *lt, *rt;
int lb, ub;
bool lazy;
Segtree(int left, int right) {
l = left;
r = right;
lt = rt = nullptr;
lb = 0;
ub = INT_MAX;
lazy = 0;
if(l == r) return;
int mid = (l+r)>>1;
lt = new Segtree(l,mid);
rt = new Segtree(mid+1,r);
}
void propagate() {
if(lazy) {
if(lt){
// cerr << "from propagation ";
// lt->debug();
lt->lb = max(lb, lt->lb);
lt->ub = max(lt->lb, lt->ub);
lt->ub = min(ub, lt->ub);
lt->lb = min(lt->ub, lt->lb);
rt->lb = max(lb, rt->lb);
rt->ub = max(rt->lb, rt->ub);
rt->ub = min(ub, rt->ub);
rt->lb = min(rt->ub, rt->lb);
lt->lazy = 1;
rt->lazy = 1;
lb = 0;
ub = INT_MAX;
}
lazy = 0;
}
}
void maximize(int ml, int mr, int val) {
if(l > mr or r < ml) return;
propagate();
if(ml <= l and r <= mr) {
lazy = 1;
lb = max(val,lb);
ub = max(lb,ub);
propagate();
// debug();
return;
}
lt->maximize(ml,mr,val);
rt->maximize(ml,mr,val);
// debug();
}
void minimize(int ml, int mr, int val) {
if(l > mr or r < ml) return;
propagate();
if(ml <= l and r <= mr) {
lazy = 1;
ub = min(val,ub);
lb = min(ub,lb);
propagate();
// debug();
return;
}
lt->minimize(ml,mr,val);
rt->minimize(ml,mr,val);
}
int query(int dex) {
propagate();
if(dex < l or r < dex) return 0;
// debug();
if(l == r) {
return lb;
}
return lt->query(dex) + rt->query(dex);
}
void debug() {
cerr << "node " << l << " " << r << " bounds " << lb << " " << ub << endl;
}
void preorder() {
propagate();
debug();
if(lt) {
lt->preorder();
rt->preorder();
}
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segtree st(0,n-1);
for(int i = 0; i < k; i++) {
bool type = (op[i] == 1 ? 1 : 0);
if(type) {
// add aka maximize
st.maximize(left[i],right[i],height[i]);
} else {
st.minimize(left[i],right[i],height[i]);
}
}
// st.preorder();
for(int i = 0; i < n; i++) {
finalHeight[i] = st.query(i);
}
}
