#include "wall.h"
#define INF 0x7fffffff
int N, M, Idx[4194304][2], LeftBound, RightBound, Height;
void ReNewPlus(int Now)
{
if(Idx[Now][0]>Idx[Now][1])
Idx[Now][1]=Idx[Now][0];
}
void ReNewMinus(int Now)
{
if(Idx[Now][0]>Idx[Now][1])
Idx[Now][0]=Idx[Now][1];
}
void Spray(int Now)
{
if(Idx[2*Now][0]<Idx[Now][0])
Idx[2*Now][0]=Idx[Now][0];
ReNewPlus(2*Now);
if(Idx[2*Now][1]>Idx[Now][1])
Idx[2*Now][1]=Idx[Now][1];
ReNewMinus(2*Now);
if(Idx[2*Now+1][0]<Idx[Now][0])
Idx[2*Now+1][0]=Idx[Now][0];
ReNewPlus(2*Now+1);
if(Idx[2*Now+1][1]>Idx[Now][1])
Idx[2*Now+1][1]=Idx[Now][1];
ReNewMinus(2*Now+1);
Idx[Now][0]=0;
Idx[Now][1]=INF;
}
void IdxPlus(int Left, int Right, int Now)
{
int Mid;
if(LeftBound<=Left && Right<=RightBound)
{
if(Idx[Now][0]<Height)
Idx[Now][0]=Height;
ReNewPlus(Now);
}
else
{
Spray(Now);
Mid=(Left+Right)/2;
if(LeftBound<=Mid)
IdxPlus(Left,Mid,2*Now);
if(Mid+1<=RightBound)
IdxPlus(Mid+1,Right,2*Now+1);
}
}
void IdxMinus(int Left, int Right, int Now)
{
int Mid;
if(LeftBound<=Left && Right<=RightBound)
{
if(Idx[Now][1]>Height)
Idx[Now][1]=Height;
ReNewMinus(Now);
}
else
{
Spray(Now);
Mid=(Left+Right)/2;
if(LeftBound<=Mid)
IdxMinus(Left,Mid,2*Now);
if(Mid+1<=RightBound)
IdxMinus(Mid+1,Right,2*Now+1);
}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
int i;
N=n;
for(M=1 ; M<N ; M*=2);
for(i=2 ; i<2*M ; i++)
Idx[i][1]=INF;
for(i=0 ; i<k ; i++)
{
LeftBound=left[i];
RightBound=right[i];
Height=height[i];
if(op[i]==1)
IdxPlus(0,M-1,1);
else
IdxMinus(0,M-1,1);
}
for(i=1 ; i<M ; i++)
Spray(i);
for(i=M ; i<M+N ; i++)
finalHeight[i-M]=Idx[i][0];
}
