#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
#include "wall.h"
ii combine(ii p1, ii p2) { // apply p1 on p2 (p1 is newer)
// (a, b) [later] done on (c, d)
// becomes (max(a, c), min(b, d))
// if min(b, d) > max(a, c), know that [a, b] and [c, d] are disjoint
// if b < d, then becomes (b, b); otherwise becomes (c, c)
ii res = {max(p1.fi, p2.fi), min(p1.se, p2.se)};
if (res.fi > res.se) {
if (p1.se < p2.se)
res = {p1.se, p1.se};
else
res = {p1.fi, p1.fi};
}
return res;
}
struct Segtree { // range addition, range sum query
int sz;
vector<ii> lazy; // store (a, b)
Segtree(int N) {
sz = 1;
while (sz < N)
sz *= 2;
lazy = vector<ii>(2 * sz, {-1e9, 1e9});
}
void push(int id, int left, int right) {
if (right - left == 1)
return;
lazy[2 * id + 1] = combine(lazy[id], lazy[2 * id + 1]);
lazy[2 * id + 2] = combine(lazy[id], lazy[2 * id + 2]);
lazy[id] = {-1e9, 1e9};
}
void range_upd(int qleft, int qright, ii val, int id, int left, int right) {
if (qleft <= left && right <= qright) {
lazy[id] = combine(val, lazy[id]);
return;
}
if (qright <= left || right <= qleft)
return;
push(id, left, right);
int mid = (left + right) / 2;
range_upd(qleft, qright, val, 2 * id + 1, left, mid);
range_upd(qleft, qright, val, 2 * id + 2, mid, right);
}
void range_upd(int qleft, int qright, ii val) {
range_upd(qleft, qright, val, 0, 0, sz);
}
ii query(int pos, int id, int left, int right) {
if (right - left == 1) {
return lazy[id];
}
push(id, left, right);
int mid = (left + right) / 2;
if (pos < mid)
return query(pos, 2 * id + 1, left, mid);
else
return query(pos, 2 * id + 2, mid, right);
}
ii query(int pos) {
return query(pos, 0, 0, sz);
}
};
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
Segtree st(N);
for (int i = 0; i < K; i++) {
if (op[i] == 1)
st.range_upd(left[i], right[i] + 1, {height[i], 1e9});
else
st.range_upd(left[i], right[i] + 1, {-1e9, height[i]});
}
/* for (int i = 0; i < N; i++) {
ii res = st.query(i);
cout<<i<<": "<<res.fi<<" "<<res.se<<endl;
}*/
for (int i = 0; i < N; i++) {
finalHeight[i] = max(st.query(i).fi, 0);
}
return;
}
// f(x) = a, x, or b (piecewise)
// represent function
// store as (a, b), where a can be -inf and b can be +inf
// query: returns (a, b)
// (a, b) [later] done on (c, d)
// becomes (max(a, c), min(b, d))
// if min(b, d) > max(a, c), know that [a, b] and [c, d] are disjoint
// if b < d, then becomes (b, b); otherwise becomes (c, c)
