#include "wall.h"
/** * * * * * * * * * * * * * **\
* *
* Author: Haidara Nassour *
* Coded in: YYYY\M\D HH:MM:SS *
* Lang: C++ *
* *
\** * * * * * * * * * * * * * **/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define itn int
#define rep(i,x,n) for(int i=(x);i<(n);i++)
#define FOR(i,n) rep(i,0,n)
#define per(i,x,n) for(int i=(x);i>(n);i--)
#define ROF(i,x) for(int i=x;i>=0;i--)
#define v(i) vector< i >
#define p(i,j) pair< i , j >
#define pii pair<int,int>
#define m(i,j) map< i , j >
#define um(i,j) unordered_map< i , j >
#define max_heap(i) priority_queue< i >
#define min_heap(i) priority_queue< i , vector< i > ,greater< i > >
#define ff first
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ss second
#define pp push_back
#define mini(x,y) x=min(x,y)
#define maxi(x,y) x=max(x,y)
#define debug(x) cout<<#x<<" ";
using namespace std;
using namespace __gnu_pbds;
void SIO(string name="")
{
if(name!="")
{
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
}
template <class T> using o_set = tree<T, null_type, less<T>,rb_tree_tag, tree_order_statistics_node_update>;
///order_of_key = find index of element x ( returned val is integer )
///find_by_order = find value at index x ( returned val is pointer )
const double pi=2.0*acos(0.0);
const int mod=1e9+7;
const int maxn=2000001;
const int inf=1e9+7;
struct segtree
{
int mx=inf,mn=0;
segtree():mn(0),mx(inf){}
} st[maxn*4];
bool add=0;
void pull(int inx)
{
st[inx*2].mn=max(min(st[inx].mx,st[inx*2].mn),st[inx].mn);
st[inx*2].mx=min(max(st[inx*2].mx,st[inx].mn),st[inx].mx);
st[inx*2+1].mn=max(min(st[inx*2+1].mn,st[inx].mx),st[inx].mn);
st[inx*2+1].mx=min(max(st[inx*2+1].mx,st[inx].mn),st[inx].mx);
st[inx].mn=0;
st[inx].mx=inf;
}
void update(int ul,int ur,int val,int l,int r,int inx=1)
{
if(ul<=l&&r<=ur)
{
if(add)
{
st[inx].mn=max(st[inx].mn,val);
st[inx].mx=max(st[inx].mn,st[inx].mx);
}
else
{
st[inx].mx=min(st[inx].mx,val);
st[inx].mn=min(st[inx].mn,st[inx].mx);
}
if(l!=r)
pull(inx);
return ;
}
if(l>ur||ul>r)
return ;
pull(inx);
int mid=l+(r-l)/2;
update(ul,ur,val,l,mid,inx*2);
update(ul,ur,val,mid+1,r,inx*2+1);
}
int query(int pos,int l,int r,int inx=1)
{
if(l==r)
return st[inx].mn;
int mid=l+(r-l)/2;
pull(inx);
if(pos<=mid)
return query(pos,l,mid,inx*2);
return query(pos,mid+1,r,inx*2+1);
}
void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[])
{
for(int i=0; i<k; i++)
{
if(op[i]==1)
add=1;
else
add=0;
update(left[i]+1,right[i]+1,height[i],1,n);
}
for(int i=0; i<n; i++)
finalHeight[i]=query(i+1,1,n);
}
