#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);
struct segtree {
int l, r;
segtree *left, *right;
int down, up;
void merge() {
;; // nothing??
}
void update(pair<int, int> upd) {
down = max(down, upd.first);
up = max(up, down);
up = min(up, upd.second);
down = min(down, up);
}
segtree(int l, int r) : l(l), r(r) {
down = 0;
up = INT_MAX;
if (l == r) {
left = right = nullptr;
return;
}
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
merge();
}
void propagate() {
if (left) {
left->update({down, up});
right->update({down, up});
down = 0;
up = INT_MAX;
}
}
int query(int ind) {
if (l == r) {
return down;
}
int m = (l+r)/2;
propagate();
if (ind <= m) return left->query(ind);
else return right->query(ind);
}
void updateUp(int ql, int qr, int upd) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
update({0, upd});
propagate();
return;
}
int m = (l+r)/2;
propagate();
left->updateUp(ql, qr, upd);
right->updateUp(ql, qr, upd);
}
void updateDown(int ql, int qr, int upd) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
update({upd, INT_MAX});
propagate();
return;
}
int m = (l+r)/2;
propagate();
left->updateDown(ql, qr, upd);
right->updateDown(ql, qr, upd);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segtree st(0, n-1);
REP(i, 0, k) {
if (op[i] == 1) {
st.updateDown(left[i], right[i], height[i]);
}
else {
st.updateUp(left[i], right[i], height[i]);
}
}
// this should be an insignificant until subtask 3, optimize by storing nodes later:P
REP(i, 0, n) {
finalHeight[i] = st.query(i);
// cerr << st.query(i) << endl;
}
return;
}
// signed main() {
// int n, k; cin >> n >> k;
// int op[k], left[k], right[k], height[k], finalHeight[n];
// fill_n(finalHeight, n, 0);
// REP(i, 0, k) {
// cin >> op[i] >> left[i] >> right[i] >> height[i];
// }
// buildWall(n, k, op, left, right, height, finalHeight);
// for (auto &x : finalHeight) {
// cout << x << endl;
// }
// cout << endl;
// }
