/*
im gonna copy gabee's style of making the top row my thinking space
idea: store a segment tree that lazily stores each update.
what will each range contain? it will contain the minimum and maximum value of each range. thus, the updates get reworded as:
add -> replace both values with max(self, v)
remove -> replace both values with min(self, v)
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
struct ST{
int mn, mx;
ST *lt, *rt;
int l, r;
bool lazy;
void combine() {
mn = min(lt->mn, rt->mn);
mx = max(lt->mx, rt->mx);
}
void prop() {
if(!lazy) return;
if(lt) {
lt->mn = mn;
lt->mx = mx;
rt->mn = mn;
rt->mx = mx;
lt->lazy = true;
rt->lazy = true;
}
lazy = false;
}
ST(ll bl, ll br) {
l = bl; r = br;
lt = rt = nullptr;
mn = mx = 0;
lazy = false;
if(l != r) {
ll m = (l+r)>>1;
lt = new ST(l, m);
rt = new ST(m+1, r);
}
}
void addUpd(int ql, int qr, int qv) {
prop();
if(qr < l || r < ql || mn >= qv) return;
if(ql <= l && r <= qr && mn == mx) {
mn = max(mn, qv);
mx = max(mn, qv);
lazy = true;
prop();
return;
}
if(!lt) return;
lt->addUpd(ql, qr, qv);
rt->addUpd(ql, qr, qv);
combine();
}
void remUpd(int ql, int qr, int qv) {
prop();
if(qr < l || r < ql || mx <= qv) return;
if(ql <= l && r <= qr && mn == mx) {
mn = min(mn, qv);
mx = min(mx, qv);
lazy = true;
prop();
return;
}
if(!lt) return;
lt->remUpd(ql, qr, qv);
rt->remUpd(ql, qr, qv);
combine();
}
int qry(int i) {
prop();
if(i < l || r < i) return -1;
if(l == r && r == i) {return mn;}
return max(lt->qry(i), rt->qry(i));
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
ST tree(0, n-1);
for(int i = 0; i < k; i++) {
if(op[i] == 1) { // add
tree.addUpd(left[i], right[i], height[i]);
} else {
tree.remUpd(left[i], right[i], height[i]);
}
}
for(int i = 0; i < n; i++) {
finalHeight[i] = tree.qry(i);
}
}
