#include "wall.h"
#include <bits/stdc++.h>
#define ll long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define count1 __builtin_popcount
#define all(v) v.begin(), v.end()
using namespace std;
struct point{
int ma, mi;
};
constexpr int MAX = 2e+6 + 3, INF = 2e+9, MOD = 1e+9 + 7, K = log2(MAX);
vector <point> t(4 * MAX, {0, 0}), lazy(4 * MAX, {-1, INF});
vector <int> h;
void push(int v) {
if (lazy[v].ma > lazy[v].mi) {
lazy[v].ma = -1;
}
if (lazy[v].ma != -1) {
if (t[v*2].mi < lazy[v].ma) {
t[v*2].mi = lazy[v].ma;
t[v*2].ma = max(t[v*2].ma, t[v*2].mi);
lazy[v*2].ma = max(lazy[v*2].ma, lazy[v].ma);
}
if (t[v*2+1].mi < lazy[v].ma) {
t[v*2+1].mi = lazy[v].ma;
t[v*2+1].ma = max(t[v*2+1].ma, t[v*2+1].mi);
lazy[v*2+1].ma = max(lazy[v*2+1].ma, lazy[v].ma);
}
lazy[v].ma = -1;
}
if (lazy[v].mi != INF) {
if (t[v*2].ma > lazy[v].mi) {
t[v*2].ma = lazy[v].mi;
t[v*2].mi = min(t[v*2].mi, t[v*2].ma);
lazy[v*2].mi = min(lazy[v*2].mi, lazy[v].mi);
}
if (t[v*2+1].ma > lazy[v].mi) {
t[v*2+1].ma = lazy[v].mi;
t[v*2+1].mi = min(t[v*2+1].mi, t[v*2+1].ma);
lazy[v*2+1].mi = min(lazy[v*2+1].mi, lazy[v].mi);
}
lazy[v].mi = INF;
}
}
void update1(int v, int tl, int tr, int l, int r, int x) { // increase
if (l > r) return;
if (tl == l && tr == r) {
if (t[v].mi < x) {
lazy[v].ma = max(lazy[v].ma, x);
if (lazy[v].mi < lazy[v].ma) {
lazy[v].mi = INF;
}
t[v].mi = x;
t[v].ma = max(t[v].ma, t[v].mi);
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update1(v*2, tl, tm, l, min(r, tm), x);
update1(v*2+1, tm+1, tr, max(l, tm+1), r, x);
t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}
void update2(int v, int tl, int tr, int l, int r, int x) { // decrease
if (l > r) return;
if (tl == l && tr == r) {
if (t[v].ma > x) {
lazy[v].mi = min(lazy[v].mi, x);
if (lazy[v].mi < lazy[v].ma) {
lazy[v].ma = -1;
}
t[v].ma = x;
t[v].mi = max(t[v].ma, t[v].mi);
}
return;
}
push(v);
int tm = (tl + tr) / 2;
update2(v*2, tl, tm, l, min(r, tm), x);
update2(v*2+1, tm+1, tr, max(l, tm+1), r, x);
t[v].ma = max(t[v*2].ma, t[v*2+1].ma);
t[v].mi = min(t[v*2].mi, t[v*2+1].mi);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
h.pb(t[v].ma);
return;
}
push(v);
int tm = (tl + tr) / 2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for (int z=0; z < k; z++) {
if (op[z] == 1) {
update1(1, 0, n-1, left[z], right[z], height[z]);
}
else {
update2(1, 0, n-1, left[z], right[z], height[z]);
}
}
build(1, 0, n-1);
for (int i=0; i < n; i++) {
finalHeight[i] = h[i];
}
return;
}
