#include "wall.h"
#include "bits/stdc++.h"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using ll = long long;
using ull = unsigned long long;
using pairll = std::pair<ll, ll>;
using pairi = std::pair<int, int>;
using namespace std;
#define forn(i, n) for (ll i = 0; i < (n); ++i)
#define fora(i, a, b) for (ll i = (a); i <= (b); ++i)
#define ford(i, a, b) for (ll i = (a); i >= (b); --i)
#define to_int(x) static_cast<int>((x))
#define to_long(x) static_cast<long>((x))
#define to_ll(x) static_cast<long long>((x))
#define all(v) (v).begin(), (v).end()
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define LSB(x) ((x) & -(x))
#define LSBPos(x) to_ll(log2(LSB(x)))
#define contains(container, x) ((container).find((x)) != (container).end())
#define CMP(name, type, body) \
struct name { \
bool operator()(const type &a, const type &b) const { return (body); } \
};
#define foreach(v, i) for (auto i = (v).begin(); i != (v).end(); ++i)
#define debug(x) std::cout << #x << " = " << (x) << std::endl
#define print_vec(v) \
do { \
for (const auto &val : (v)) \
std::cout << val << " "; \
std::cout << std::endl; \
} while (0);
#define print_pair(p) \
std::cout << "(" << (p).first << ", " << (p).second << ")" << std::endl
#define print_mat(m) \
for (const auto &vec : m) \
print_vec(vec)
/* Custom printing statements */
void print(string s) { cout << s << endl; }
void print_set(set<ll> s) {
for (auto it = s.begin(); it != s.end(); ++it)
cout << *it << " ";
cout << endl;
}
void print_map(map<ll, ll> m) {
for (auto it = m.begin(); it != m.end(); ++it) {
cout << it->first << "->" << it->second;
cout << endl;
}
cout << endl;
}
template <typename T> void print_pq(T pq) {
cout << "pq: ";
while (!pq.empty()) {
ll top = pq.top();
pq.pop();
cout << top << ", ";
}
cout << endl;
}
class LazySegmentTree {
public:
int n;
vector<ll> t;
vector<ll> lazy_min, lazy_max;
vector<bool> is_min_first;
LazySegmentTree(int size)
: n{size}, t{vector<ll>(4 * size, 0ll)},
lazy_min{vector<ll>(4 * size, LLONG_MIN)},
lazy_max{vector<ll>(4 * size, LLONG_MAX)},
is_min_first{vector<bool>(4 * size, false)} {}
void modify(int l, int r, ll v, bool is_min) {
modify(l, r, v, is_min, 0, 0, n);
}
void modify(int l, int r, ll v, bool is_min, int x, int lx, int rx) {
if (lx >= r || l >= rx) {
return;
}
// Current range encompasses target range
if (lx >= l && r >= rx) {
if (is_min) {
apply(v, LLONG_MAX, is_min, x, lx, rx);
} else {
apply(LLONG_MIN, v, is_min, x, lx, rx);
}
return;
}
// Target range is somewhere further down
push(x, lx, rx);
int mid = (lx + rx) / 2;
modify(l, r, v, is_min, x * 2 + 1, lx, mid);
modify(l, r, v, is_min, x * 2 + 2, mid, rx);
t[x] = t[x * 2 + 1] + t[x * 2 + 2];
}
ll query(int l, int r) { return query(l, r, 0, 0, n); }
ll query(int l, int r, int x, int lx, int rx) {
if (lx >= r || l >= rx) {
return 0;
}
if (lx >= l && rx <= r) {
return t[x];
}
push(x, lx, rx);
int mid = (lx + rx) / 2;
ll left_res = query(l, r, x * 2 + 1, lx, mid);
ll right_res = query(l, r, x * 2 + 2, mid, rx);
return left_res + right_res;
}
void push(int x, int lx, int rx) {
// Leaf node
if (rx - lx == 1) {
return;
}
int mid = (lx + rx) / 2;
apply(lazy_min[x], lazy_max[x], is_min_first[x], x * 2 + 1, lx, mid);
apply(lazy_min[x], lazy_max[x], is_min_first[x], x * 2 + 2, mid, rx);
lazy_max[x] = LLONG_MAX;
lazy_min[x] = LLONG_MIN;
// is_min_first[x] = false;
}
// Propogate val to x
void apply(ll set_min, ll set_max, bool min_first, int x, int lx, int rx) {
int affected_count = rx - lx;
if (!min_first) {
t[x] = max(t[x], set_min);
t[x] = min(t[x], set_max);
} else {
t[x] = min(t[x], set_max);
t[x] = max(t[x], set_min);
}
lazy_min[x] = max(lazy_min[x], set_min);
lazy_max[x] = min(lazy_max[x], set_max);
is_min_first[x] = min_first;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[],
int finalHeight[]) {
LazySegmentTree t(n);
for (int i = 0; i < k; i++) {
int type = op[i];
int l = left[i];
int r = right[i];
int x = height[i];
r++;
// Add
// Min height = x
if (type == 1) {
t.modify(l, r, x, true);
}
// Remove
// Max height = x
if (type == 2) {
t.modify(l, r, x, false);
}
}
for (int i = 0; i < n; i++) {
// cout << t.query(i, i + 1) << endl;
finalHeight[i] = t.query(i, i + 1);
}
}
