#include<bits/stdc++.h>
#include "wall.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
vector<ll> vec;
vector<pair<ll,ll> > tr;
void build(ll ind, ll l, ll r){
if(l == r){tr[ind]={0,0};return ;}
build(ind*2, l, (l+r)/2);
build(ind*2+1, (l+r)/2+1, r);
return ;
}
void fun(ll ind, ll l, ll r, ll x, ll y, ll a, ll b){
if(y < l || x > r)return ;
if(x <= l && r <= y){
if(b <= tr[ind].first)tr[ind] = {b, b};
else if(a >= tr[ind].second)tr[ind] = {a, a};
else {
tr[ind].first = max(tr[ind].first, a);
tr[ind].second = min(tr[ind].second, b);
}
return ;
}
if(tr[ind] != make_pair(ll(-1), LONG_LONG_MAX)){
fun(ind*2, l, (l+r)/2, l, (l+r)/2, tr[ind].first, tr[ind].second);
fun(ind*2+1, (l+r)/2+1, r, (l+r)/2+1, r, tr[ind].first, tr[ind].second);
tr[ind].first = -1;
tr[ind].second = LONG_LONG_MAX;
}
fun(ind*2, l, (l+r)/2, x, y, a, b);
fun(ind*2+1, (l+r)/2+1, r, x, y, a, b);
return ;
}
void fin(ll ind, ll l, ll r, ll a, ll b){
if(b <= tr[ind].first)tr[ind] = {b, b};
else if(a >= tr[ind].second)tr[ind] = {a, a};
else {
tr[ind].first = max(tr[ind].first, a);
tr[ind].second = min(tr[ind].second, b);
}
if(l == r){vec[l]= max(tr[ind].first, a);return ;}
fin(ind*2, l, (l+r)/2, tr[ind].first, tr[ind].second);
fin(ind*2+1, (l+r)/2+1, r, tr[ind].first, tr[ind].second);
return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vec.assign(n+1, 0);
tr.assign(4*n+1, {-1, LONG_LONG_MAX});
build(1, 1, n);
for(int i=0;i<k;i++){
op[i]==1?fun(1, 1, n, left[i]+1, right[i]+1, height[i], LONG_LONG_MAX):fun(1, 1, n, left[i]+1, right[i]+1, -1, height[i]);
}
fin(1, 1, n, -1, LONG_LONG_MAX);
for(int i=1;i<=n;i++){finalHeight[i-1] = vec[i];}
return;
}
