#include "wall.h"
#include<algorithm>
using namespace std;
int c=1;
struct data
{
int mini,maxi;
}tree[4194400];
void spread(int k)
{
if(tree[k*2].mini<tree[k].mini)
{
tree[k*2].mini=tree[k].mini;
tree[k*2].maxi=max(tree[k*2].maxi,tree[k*2].mini);
}
if(tree[k*2].maxi>tree[k].maxi)
{
tree[k*2].maxi=tree[k].maxi;
tree[k*2].mini=min(tree[k*2].mini,tree[k*2].maxi);
}
if(tree[k*2+1].mini<tree[k].mini)
{
tree[k*2+1].mini=tree[k].mini;
tree[k*2+1].maxi=max(tree[k*2+1].maxi,tree[k*2+1].mini);
}
if(tree[k*2+1].maxi>tree[k].maxi)
{
tree[k*2+1].maxi=tree[k].maxi;
tree[k*2+1].mini=min(tree[k*2+1].mini,tree[k*2+1].maxi);
}
}
void Plus(int k,int x,int y,int s,int e,int h)
{
if(y<s || x>e) return;
if(x>=s && y<=e)
{
tree[k].mini=max(tree[k].mini,h);
tree[k].maxi=max(tree[k].maxi,tree[k].mini);
return;
}
spread(k);
Plus(k*2,x,(x+y)/2,s,e,h);
Plus(k*2+1,(x+y)/2+1,y,s,e,h);
tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void Minus(int k,int x,int y,int s,int e,int h)
{
if(y<s || x>e) return;
if(x>=s && y<=e)
{
tree[k].maxi=min(h,tree[k].maxi);
tree[k].mini=min(tree[k].mini,tree[k].maxi);
return;
}
spread(k);
Minus(k*2,x,(x+y)/2,s,e,h);
Minus(k*2+1,(x+y)/2+1,y,s,e,h);
tree[k].mini=min(tree[k*2].mini,tree[k*2+1].mini);
tree[k].maxi=max(tree[k*2].maxi,tree[k*2+1].maxi);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
int i;
for(i=1;;i++)
{
if(c>=n) break;
c*=2;
}
for(i=0;i<k;i++)
{
if(op[i]==1) Plus(1,1,c,left[i]+1,right[i]+1,height[i]);
else Minus(1,1,c,left[i]+1,right[i]+1,height[i]);
}
for(i=1;i<c;i++)
{
if(i==11)
{
i=11;
}
spread(i);
}
for(i=c;i<=c+n-1;i++)
{
finalHeight[i-c]=tree[i].mini;
}
return;
}
