#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 ;
#define maxn 2000009
#define left id<<1
#define right id<<1|1
struct shape{
int Min , Max ;
} T [maxn*4] ;
void fmax ( int id , int w )
{
if ( T[id].Min < w ) T [id].Min = w ;
if ( T[id].Max < w ) T [id].Max = w ;
}
void fmin ( int id , int w )
{
if ( T[id].Min > w ) T [id].Min = w ;
if ( T[id].Max > w ) T [id].Max = w ;
}
void down ( int id )
{
fmax (left,T[id].Max) , fmax (right,T[id].Max) ;
fmin (left,T[id].Min) , fmin (right,T[id].Min) ;
T [id].Max = 0 , T [id].Min = INF ;
}
void update ( int id , int l , int r , int u , int v , int w , int type )
{
if ( l > v || r < u ) return ;
if ( u <= l && r <= v )
{
if ( type == 1 ) fmax (id,w) ;
else fmin (id,w) ;
return ;
}
down (id) ;
int mid = (l+r)/2 ;
update (left,l,mid,u,v,w,type) ;
update (right,mid+1,r,u,v,w,type) ;
}
int get ( int id , int l , int r , int pos )
{
if ( l > pos || r < pos ) return 0 ;
if ( l == r ) return T [id].Max ;
down (id) ;
int mid = (l+r)/2 ;
return max(get(left,l,mid,pos),get(right,mid+1,r,pos)) ;
}
void buildWall(int n, int k, int op[], int l[], int r[], int height[], int finalHeight[]){
for ( int i = 0 ; i < n*4 ; i ++ ) T [i].Min = INF ;
for ( int i = 0 ; i < k ; i ++ )
{
update (1,0,n-1,l[i],r[i],height[i],op[i]) ;
}
for ( int i = 0 ; i < n ; i ++ ) finalHeight [i] = get (1,0,n-1,i) ;
return ;
}
