#include "wall.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll i,mi[8080808],ma[8080808],h[2020202];
void tum(ll aa,ll bb,ll cc)
{
mi[aa]=min(mi[aa],bb);
ma[aa]=min(ma[aa],bb);
ma[aa]=max(ma[aa],cc);
}
void upd(ll aa,ll bb,ll cc,ll dd,ll ee,ll ff,ll gg)
{
if(aa==bb)
h[aa]=ma[ee];
else
if(mi[ee]!=1e17||ma[ee]!=0)
{
tum(ee*2,mi[ee],ma[ee]);
tum(ee*2+1,mi[ee],ma[ee]);
mi[ee]=1e17;
ma[ee]=0;
}
if(bb<cc||dd<aa)
return ;
else
if(cc<=aa&&bb<=dd)
tum(ee,ff,gg);
else
{
upd(aa,(aa+bb)/2,cc,dd,ee*2,ff,gg);
upd((aa+bb)/2+1,bb,cc,dd,ee*2+1,ff,gg);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(i=1;i<=4*n;i++)
mi[i]=1e17;
for(i=0;i<k;i++)
if(op[i]==1)
upd(0,n-1,left[i],right[i],1,1e17,height[i]);
else
upd(0,n-1,left[i],right[i],1,height[i],0);
for(i=0;i<n;i++)
upd(0,n-1,i,i,1,1e17,0);
for(i=0;i<n;i++)
finalHeight[i]=h[i];
}
