#include "wall.h"
#include <iostream>
using namespace std;
int nn;
const int maxn = 2000005;
struct Wall{
int max,min,val;
}wall[maxn*4];
int fh[maxn];
void add(int p,int x,int y,int tx,int ty,int h)
{
int mid=(x+y)/2;
if(y<tx || ty<x)return ;
if(tx<=x && y<=ty) // xy在txty中
{
if(h>=wall[p].max) // 高度大於區間最高值 全部改
{
wall[p].max=h;
wall[p].min=h;
return ;
}
else if(h<wall[p].min)return ;//高度小於區間最小
}
if(wall[p].max == wall[p].min)
{
wall[p*2].max=wall[p*2+1].max=wall[p].max;
wall[p*2].min=wall[p*2+1].min=wall[p].min;
}
add(p*2,x,mid,tx,ty,h);
add(p*2+1,mid+1,y,tx,ty,h);
wall[p].max=max(wall[p*2].max,wall[p*2+1].max);
wall[p].min=min(wall[p*2].min,wall[p*2+1].min);
return ;
}
void rmv(int p,int x,int y,int tx,int ty,int h)
{
int mid=(x+y)/2;
if(y<tx || ty<x)return ;
if(tx<=x && y<=ty) // xy在txty中
{
if(h<=wall[p].min) // 高度小於區間最低值 全部改
{
wall[p].max=h;
wall[p].min=h;
return ;
}
else if(h>wall[p].max)return ;//高度大於區間最大 捨去
}
if(wall[p].max == wall[p].min)
{
wall[p*2].max=wall[p*2+1].max=wall[p].max;
wall[p*2].min=wall[p*2+1].min=wall[p].min;
}
rmv(p*2,x,mid,tx,ty,h);
rmv(p*2+1,mid+1,y,tx,ty,h);
wall[p].max=max(wall[p*2].max,wall[p*2+1].max);
wall[p].min=min(wall[p*2].min,wall[p*2+1].min);
return ;
}
void find(int p,int x,int y)
{
if(wall[p].max==wall[p].min)
{
for(int i=x;i<=y;i++)fh[i]=wall[p].min;
return ;
}
int mid=(x+y)/2;
find(p*2,x,mid);
find(p*2+1,mid+1,y);
return ;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++)
{
if(op[i]==1)add(1,0,n-1,left[i],right[i],height[i]);
if(op[i]==2)rmv(1,0,n-1,left[i],right[i],height[i]);
//find(1,0,n-1);
//for(int i=0;i<n;i++)cout<<fh[i]<<" ";
//cout<<endl;
}
find(1,0,n-1);
for(int i=0;i<n;i++)finalHeight[i]=fh[i];
return;
}
