#include <bits/stdc++.h>
#include "wall.h"
#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;
template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 2e6 + 10;
const int inf = 1e9;
struct node
{
int mi, ma;
node() : mi(0), ma(0) {}
node(int mi, int ma) : mi(mi), ma(ma) {}
} f[maxN * 4];
int L, R, val;
int *ans;
void down(int x)
{
uin(f[x * 2 + 1].mi, f[x].mi);
uin(f[x * 2 + 1].ma, f[x * 2 + 1].mi);
uax(f[x * 2 + 1].ma, f[x].ma);
uax(f[x * 2 + 1].mi, f[x * 2 + 1].ma);
uin(f[x * 2 + 2].mi, f[x].mi);
uin(f[x * 2 + 2].ma, f[x * 2 + 2].mi);
uax(f[x * 2 + 2].ma, f[x].ma);
uax(f[x * 2 + 2].mi, f[x * 2 + 2].ma);
}
void minimize(int x, int lo, int hi)
{
if (lo > R || hi < L)
{
return;
}
if (lo >= L && hi <= R)
{
uin(f[x].mi, val);
uin(f[x].ma, f[x].mi);
return;
}
down(x);
int mid = (lo + hi) / 2;
minimize(x * 2 + 1, lo, mid);
minimize(x * 2 + 2, mid + 1, hi);
f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}
void maximize(int x, int lo, int hi)
{
if (lo > R || hi < L)
{
return;
}
if (lo >= L && hi <= R)
{
uax(f[x].ma, val);
uax(f[x].mi, f[x].ma);
return;
}
down(x);
int mid = (lo + hi) / 2;
maximize(x * 2 + 1, lo, mid);
maximize(x * 2 + 2, mid + 1, hi);
f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}
void build(int x, int lo, int hi)
{
if (lo == hi)
{
ans[lo] = f[x].mi;
return;
}
down(x);
int mid = (lo + hi) / 2;
build(x * 2 + 1, lo, mid);
build(x * 2 + 2, mid + 1, hi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for0(i, k)
{
if (op[i] == 1)
{
//adding phase
L = left[i], R = right[i], val = height[i];
maximize(0, 0, n - 1);
}
else
{
//removing phase
L = left[i], R = right[i], val = height[i];
minimize(0, 0, n - 1);
}
}
ans = finalHeight;
build(0, 0, n - 1);
}
