#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
// const int N=2e6+10;
// int val[N];
const int inf=1e9;
struct SegmentTree
{
int mx=-inf,mi=inf;
// v will change to min(mi,max(v,mx))
SegmentTree *next[2];
int l,r;
SegmentTree(int s,int e)
{
l=s,r=e;
if(l==r)
{
return;
}
int mid=(l+r)/2;
next[0]=new SegmentTree(s,mid);
next[1]=new SegmentTree(mid+1,e);
}
void propagate()
{
next[0]->mx=min(mi,max(mx,next[0]->mx));
next[0]->mi=min(mi,max(mx,next[0]->mi));
next[1]->mx=min(mi,max(mx,next[1]->mx));
next[1]->mi=min(mi,max(mx,next[1]->mi));
mx=-inf;
mi=inf;
}
void Update(int ql,int qr,int v,bool ty) // ty=0 for max operation
{
// cout<<ql<<' '<<qr<<' '<<l<<' '<<r<<endl;
if(r<ql or qr<l)return;
if(ql<=l and r<=qr)
{
// min(mi,max(mx,prev))
// mx<=mi
// prev < mx mx
// mx<=prev<=mi prev
// mi < prev mi
if(!ty)
{
mx=max(mx,v);
mi=max(mi,v);
}
else{
mx=min(mx,v);
mi=min(mi,v);
}
return;
}
// send the current nodes update down
propagate();
next[0]->Update(ql,qr,v,ty);
next[1]->Update(ql,qr,v,ty);
}
int get(int i,int o)
{
if(l==r)
{
return min(mi,max(mx,o));
}
propagate();
return next[(i>((l+r)/2))]->get(i,o);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
// for(int i=0;i<n;i++)
// {
// val[i]=
// }
// cout<<"Here6"<<endl;
SegmentTree* sg=new SegmentTree(0,n-1);
// cout<<"Here3"<<endl;
for(int i=0;i<k;i++)
{
// cout<<"Here2"<<endl;
// left[i]--;
// right[i]--;
sg->Update(left[i],right[i],height[i],op[i]-1);
}
for(int i=0;i<n;i++)
{
// cout<<""
finalHeight[i]=sg->get(i,0);
}
return;
}
