#include <algorithm>
#include <cmath>
#include <iostream>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <climits>
#define all(a) (a).begin(), (a).end()
#define allr(a) (a).rbegin(), (a).rend()
#define ll long long
#define fr(i, a, b) for (ll i = a; i < b; i++)
#define fr1(i, a, b) for (ll i = a - 1; i >= b; i--)
#define fi first
#define se second
#define mp(j, k) make_pair(j, k)
#define pb(x) push_back(x)
#define pbp(x, y) push_back({x, y})
#define in(x) insert(x)
#define vec vector<ll>
#define vecv vector<vector<ll> >
#define veb vector<bool>
#define vecp vector<pair<ll,ll>>
#define yes cout << "YES\n";
#define no cout << "NO\n";
#define ac 1e-7
#define fauto(a) \
for (auto i : a) \
cout << i << " ";
#define fautop(a) \
for (auto i : a) \
cout << i.fi << " " << i.se << endl;
using namespace std;
struct Node
{
int l, r;
int mn, mx;
int lazyS;
int lazy;
};
static vector<Node> ST;
void build(int node, int l, int r)
{
ST[node].l = l;
ST[node].r = r;
ST[node].mn = 0;
ST[node].mx = 0;
ST[node].lazy = 0;
ST[node].lazyS = true;
if(l == r) return;
int mid = (l + r) / 2;
int left = node * 2;
int right = node * 2 + 1;
build(left, l, mid);
build(right, mid + 1, r);
}
void apply(int node, int val)
{
ST[node].mx = val;
ST[node].mx = val;
ST[node].lazy = val;
ST[node].lazyS = true;
}
void propagate(int node)
{
if(!ST[node].lazyS) return;
int left = node * 2;
int right = node * 2 + 1;
apply(left, ST[node].lazy);
apply(right, ST[node].lazy);
}
void pull(int node)
{
int left = node * 2;
int right = node * 2 + 1;
ST[node].mn = min(ST[left].mn, ST[right].mn);
ST[node].mx = max(ST[left].mx, ST[right].mx);
}
void updateMax(int node, int a, int b, int h)
{
int l = ST[node].l, r = ST[node].r;
if(l > b || r < a) return;
if(a <= l && r <= b)
{
if(ST[node].mx < h)
{
apply(node, h);
return;
}
if(ST[node].mn >= h) return;
}
if(l == r)
{
int newh = max(ST[node].mn, h);
apply(node, newh);
return;
}
propagate(node);
int left = node * 2;
int right = node * 2 + 1;
updateMax(left, a, b, h);
updateMax(right, a, b, h);
pull(node);
}
void updateMin(int node, int a, int b, int h)
{
int l = ST[node].l, r = ST[node].r;
if(l > b || r < a) return;
if(a <= l && r <= b)
{
if(ST[node].mn > h)
{
apply(node, h);
return;
}
if(ST[node].mx <= h) return;
}
if(l == r)
{
int newh = min(ST[node].mn, h);
apply(node, newh);
return;
}
propagate(node);
int left = node * 2;
int right = node * 2 + 1;
updateMin(node, a, b, h);
updateMin(node, a, b, h);
pull(node);
}
int query(int node, int pos)
{
int l = ST[node].l, r = ST[node].r;
if(l == r) return ST[node].mn;
propagate(node);
int mid = (l + r) / 2;
int left = node * 2;
int right = node * 2 + 1;
if(pos <= mid)
{
return query(left, pos);
}
else
return query(right, pos);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
fr(i, 0, k)
{
int a = left[i];
int b = right[i];
int h = height[i];
if(op[i] == 1)
{
updateMax(1, a, b, h);
}
else
{
updateMin(1, a, b, h);
}
}
fr(i, 0, n) finalHeight[i] = query(1, i);
}
