/*
== ==
<^\()/^> <^\()/^>
\/ \/ \/ \/
/__\ . ' . /__\
== /\ . | . /\ ==
<^\()/^> !_\/ ' | ' \/_! <^\()/^>
\/ \/ !_/I_|| . ' \'/ ' . ||_I\_! \/ \/
/__\ /I_/| || -==C++==- || |\_I\ /__\
/_ \ !//| | || ' . /.\ . ' || | |\\! /_ \
(- ) /I/ | | || . | . || | | \I\ (= )
\__/!//| | | || ' | ' || | | |\\!\__/
/ \I/ | | | || ' . ' * || | | | \I/ \
{_ __} | | | || || | | | {____}
_!__|= || | | | || * + || | | | || |__!_
_I__| ||__|__|__|_|| A ||_|__|__|__||- |__I_
-|--|- ||--|--|--|-|| __/_\__ * ||-|--|--|--||= |--|-
| | || | | | || /\-'o'-/\ || | | | || | |
| |= || | | | || _||:<_>:||_ || | | | ||= | |
| |- || | | | || * /\_/=====\_/\ * || | | | ||= | |
| |- || | | | || __|:_:_[I]_:_:|__ || | | | ||- | |
_|__| ||__|__|__|_||:::::::::::::::::::::||_|__|__|__|| |__|_
-|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
jgs|- || | | | ||:::::::::::::::::::::|| | | | ||= | |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
struct SegTree {
std::vector<std::pair<int, int>> tree;
std::vector<std::pair<int, int>> lazy;
int sz;
const std::pair<int, int> identity = {-1, -1};
SegTree(const int &n) {
sz = n;
tree = std::vector<std::pair<int, int>>(sz << 2 | 1, {0, 0});
lazy = std::vector<std::pair<int, int>>(sz << 2 | 1, identity);
}
void apply(const int &id, const std::pair<int, int> &u) {
if (u.ss == 1) {
tree[id].ff = std::max(tree[id].ff, u.ff);
tree[id].ss = std::max(tree[id].ss, tree[id].ff);
} else {
tree[id].ss = std::min(tree[id].ss, u.ff);
tree[id].ff = std::min(tree[id].ff, tree[id].ss);
}
lazy[id] = u;
}
void push(const int &id) {
if (lazy[id].ff == -1)
return;
apply(id << 1, lazy[id]);
apply(id << 1 | 1, lazy[id]);
lazy[id] = {-1, -1};
}
std::pair<int, int> combine(const std::pair<int, int> &l,
const std::pair<int, int> &r) {
if (l == identity)
return r;
if (r == identity)
return l;
return std::make_pair(std::min({l.ff, l.ss, r.ff, r.ss}),
std::max({l.ff, l.ss, r.ff, r.ss}));
}
void upd(const int &id, const int &l, const int &r, const int &u,
const int &v, const int &h, const int &t) {
if (l > v || r < u)
return;
if (l >= u && r <= v)
apply(id, std::make_pair(h, t));
else {
push(id);
int m = (l + r) >> 1;
upd(id << 1, l, m, u, v, h, t);
upd(id << 1 | 1, m + 1, r, u, v, h, t);
tree[id] = combine(tree[id << 1], tree[id << 1 | 1]);
}
}
void upd(const int &l, const int &r, const int &h, const int &type) {
upd(1, 0, sz - 1, l, r, h, type);
}
std::pair<int, int> query(const int &id, const int &l, const int &r,
const int &u, const int &v) {
if (l > v || r < u)
return identity;
if (l >= u && r <= v)
return tree[id];
push(id);
int m = (l + r) >> 1;
return combine(query(id << 1, l, m, u, v),
query(id << 1 | 1, m + 1, r, u, v));
}
std::pair<int, int> query(const int &l, const int &r) {
return query(1, 0, sz - 1, l, r);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
SegTree st(n);
for (int i = 0; i < n; i++) {
st.upd(left[i], right[i], height[i], op[i]);
}
for (int i = 0; i < n; i++) {
finalHeight[i] = st.query(i, i).ff;
// std::cout << finalHeight[i] << ' ';
}
}
// int main() {
// std::ios_base::sync_with_stdio(false);
// std::cin.tie(0);
// std::cout.tie(0);
// int n, k;
// std::cin >> n >> k;
// int op[n], left[n], right[n], height[n];
// int finalHeight[n];
// for (int i = 0; i < n; i++)
// std::cin >> op[i] >> left[i] >> right[i] >> height[i];
// buildWall(n, k, op, left, right, height, finalHeight);
// }
