#include<bits/stdc++.h>
#include "wall.h"
#define ll long long
#define vl vector<ll>
#define pll pair<ll,ll>
#define in insert
#define fi first
#define se second
#define all(v) v.begin(), v.end()
using namespace std;
const ll sz = 2e6+6;
const ll dh = 1000000000;
vector<array<ll, 2>> st(sz*4), res(sz*4);
bool last[sz*4];
void comp(ll x1, ll x2){
if(st[x1][0] > st[x2][1]){
st[x2] = {st[x1][0], st[x1][0]};
}
else if(st[x1][1] < st[x2][0]){
st[x2] = {st[x1][1], st[x1][1]};
}
else{
st[x2] = {max(st[x1][0], st[x2][0]), min(st[x1][1], st[x2][1])};
}
}
void push(ll v, ll l, ll r){
if(l == r){return ;}
comp(v, v*2);
comp(v, v*2+1);
st[v] = {0, dh};
}
void upmin(ll v, ll tl, ll tr, ll l, ll r, ll val){
if(max(l, tl) > min(r, tr)){return ;}
push(v, tl, tr);
if(tl >= l && tr <= r){
if(!last[v]){
st[v] = {0ll, val};
push(v, tl, tr);
}
else{
st[v][0] = min(st[v][0], val);
st[v][1] = min(st[v][1], val);
}
return ;
}
ll tm = (tl+tr)>>1;
upmin(v*2, tl, tm, l, r, val);
upmin(v*2+1, tm+1, tr, l, r, val);
}
void upmax(ll v, ll tl, ll tr, ll l, ll r, ll val){
if(max(l, tl) > min(r, tr)){return ;}
push(v, tl, tr);
if(tl >= l && tr <= r){
if(!last[v]){
st[v] = {val, dh};
push(v, tl, tr);
}
else{
st[v][0] = max(st[v][0], val);
st[v][1] = max(st[v][1], val);
}
return ;
}
ll tm = (tl+tr)>>1;
upmax(v*2, tl, tm, l, r, val);
upmax(v*2+1, tm+1, tr, l, r, val);
}
void build(ll v, ll l, ll r){
if(l == r){
last[v] = 1;
res[v] = {0ll, 0ll};
return ;
}
ll m = (l + r)>>1;
build(v*2, l, m);
build(v*2+1, m+1, r);
}
void trav(ll v, ll tl, ll tr){
if(tl == tr){
res[tl] = st[v];
return ;
}
push(v, tl, tr);
ll tm = (tl + tr)>>1;
trav(v*2, tl, tm);
trav(v*2+1, tm+1, tr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
ll i, j, z = 0;
for(i=0;i<=(n<<2);i++){
st[i] = {0ll, dh};
}
build(1, 0, n-1);
for(i=0;i<k;i++){
if(op[i] == 1){
upmax(1, 0, n-1, left[i], right[i], height[i]);
}
else{
upmin(1, 0, n-1, left[i], right[i], height[i]);
}
}
trav(1, 0, n-1);
for(i=0;i<n;i++){
finalHeight[i] = res[i][0];
}
}
/*
10 6
1 1 8 4
0 4 9 1
0 3 6 5
1 0 5 3
1 2 2 5
0 6 7 0
*/
