#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int ma[8000000];
int mi[8000000];
int a[4000003];
int z;
int b[2000003];
int ans=0;
int n;
void push(int v)
{
//cout<<v<<endl;
if(ma[v]<ma[v*2]&&ma[v]<mi[v*2])
{
// cout<<v<<endl;
ma[v*2]=mi[v*2]=ma[v];
}else
if(mi[v]>mi[v*2]&&mi[v]>ma[v*2])
{
mi[v*2]=ma[v*2]=mi[v];
// cout<<v<<endl;
}
else
{
mi[v*2]=max(mi[v*2],mi[v]);
ma[v*2]=min(ma[v*2],ma[v]);
}
if(ma[v]<ma[v*2+1]&&ma[v]<mi[v*2+1])
{
// cout<<v<<endl;
ma[v*2+1]=mi[v*2+1]=ma[v];
}else
if(mi[v]>mi[v*2+1]&&mi[v]>ma[v*2+1])
{
// cout<<v<<endl;
mi[v*2+1]=ma[v*2+1]=mi[v];
}
else
{
mi[v*2+1]=max(mi[v*2+1],mi[v]);
ma[v*2+1]=min(ma[v*2+1],ma[v]);
}
mi[v]=0;
ma[v]=1e9;
}
void update(int v,int tl,int tr,int l,int r,int t,int val)
{
// cout<<tl<<' '<<tr<<endl;
if(l>r)
return ;
if(tl==l&&tr==r)
{
// cout<<tl<<' '<<tr<<endl;
if(t==1)
{
mi[v]=max(mi[v],val);
ma[v]=max(mi[v],ma[v]);
}else
{
ma[v]=min(ma[v],val);
mi[v]=min(mi[v],ma[v]);
}
/* if(tl==3&&tr==5)
{
// cout<<mi[v]<<' '<<ma[v]<<endl;
}*/
return ;
}
// cout<<tl<<' '<<tr<<endl;
push(v);
int tm=(tl+tr)>>1;
update(v*2,tl,tm,l,min(r,tm),t,val);
update(v*2+1,tm+1,tr,max(tm+1,l),r,t,val);
// merg(v,v*2,v*2+1);
}
int get(int v,int tl,int tr,int pos)
{
if(tl>pos||pos>tr)
return 1000000001;
if(tl==tr)
{
// cout<<ma[v]<<endl;
return mi[v];
// cout<<ma[v]<<endl;
}
push(v);
int tm=(tl+tr)/2;
return min(get(v*2,tl,tm,pos),get(v*2+1,tm+1,tr,pos));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<4*n;i++)
{
ma[i]=1000000000;
}
for(int i=0;i<k;i++)
{
update(1,0,n-1,left[i],right[i],op[i],height[i]);
}
for(int i=0;i<n;i++)
{
finalHeight[i]=get(1,0,n-1,i);
}
return ;
}
