#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
LL T;
const int INF = 1e9;
struct Info {
int L; int R;
Info() : L(-INF), R(INF) {}
Info(int L, int r) : L(L), R(R) {}
Info(int a) : L(a), R(a) {}
bool operator==(const Info& o) const {
return this->L == o.L && this->R == o.R;
}
Info& operator+=(const Info& o) {
if (o.L > this->R) {
this->L = this->R = o.L;
} else if (o.R < this->L) {
this->R = this->L = o.R;
} else {
this->L = max(this->L, o.L);
this->R = min(this->R, o.R);
}
return *this;
};
};
const Info bad = {-INF, -INF};
struct Merge {
Info operator()(const Info& a, const Info& b) {
if (a == bad) return b;
if (b == bad) return a;
Info ret;
ret.L = min(a.L, b.L);
ret.R = max(a.R, b.R);
return ret;
}
};
template<typename T, typename Merge = plus<T>, typename LazyOp=LL>
struct lazy_seg {
int n;
vector<T> tr;
vector<LazyOp> lazy_inc;
vector<bool> tag_inc;
Merge merge;
void pull(int z) {
tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
};
lazy_seg(int n) : n(n), tr(4 * n + 5), lazy_inc(4 * n + 5), tag_inc(4 * n + 5), merge(Merge()) {}
lazy_seg(vector<int> a) : lazy_seg((int)a.size()) {
function<void (int, int, int)> build = [&](int z, int l, int r) {
if (l == r) {
tr[z] = T(a[l]);
return;
}
int m = (l + r) >> 1;
build(2 * z, l, m);
build(2 * z + 1, m + 1, r);
pull(z);
};
build(1, 0, n - 1);
}
void push(int z, int l, int r) {
if (tag_inc[z]) {
tr[z] += lazy_inc[z];
//debug(z, l, r, tr[z].L, tr[z].R);
if (l < r) F0R (i, 2) {
lazy_inc[2 * z + i] += lazy_inc[z];
tag_inc[2 * z + i] = true;
}
}
tag_inc[z] = false;
lazy_inc[z] = LazyOp();
}
void up_inc(int z, int l, int r, int ql, int qr, const LazyOp& val) {
push(z, l, r);
if (ql > qr) return;
if (ql == l && qr == r) {
lazy_inc[z] += val;
tag_inc[z] = true;
push(z, l, r);
return;
}
int m = (l + r) >> 1;
up_inc(2 * z, l, m, ql, min(qr, m), val);
up_inc(2 * z + 1, m + 1, r, max(ql, m + 1), qr, val);
pull(z);
};
T query(int z, int l, int r, int ql, int qr) {
push(z, l, r);
if (ql > qr) return bad;
if (ql == l && qr == r) {
return tr[z];
}
int m = (l + r) >> 1;
return merge(
query(2 * z, l, m, ql, min(qr, m)),
query(2 * z + 1, m + 1, r, max(ql, m + 1), qr)
);
};
void up_inc(int l, int r, const LazyOp& val) { return up_inc(1, 0, n - 1, l, r, val); }
T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<int> a(n, 0);
lazy_seg<Info, Merge, Info> tree(a);
F0R (i, k) {
int T = op[i], l = left[i], r = right[i], h = height[i];
Info val;
if (T == 1) val.L = h;
else val.R = h;
tree.up_inc(l, r, val);
}
F0R (i, n) {
finalHeight[i] = tree.query(i,i).L;
}
return;
}
