#include <algorithm>
#include "wall.h"
using namespace std;
struct seg
{
int mi=0,ma=0,lazy=0;
int ty=-1;
};
seg St[262144];
void push(int i)
{
St[i*2].lazy=St[i*2+1].lazy=St[i].lazy;
St[i*2].ty=St[i*2+1].ty=St[i].ty;
St[i*2].mi=St[i*2+1].mi=St[i].lazy;
St[i*2].ma=St[i*2+1].ma=St[i].lazy;
St[i].ty=-1;
}
void add(int i,int st,int en,int l,int r,int val)
{
if (st>r||en<l)
return;
if (st>=l&&en<=r)
{
if (St[i].mi>=val)
return;
if (St[i].ma<=val)
{
St[i].mi=St[i].ma=val;
if (st!=en)
{
St[i*2].lazy=St[i*2+1].lazy=val;
St[i*2].ty=St[i*2+1].ty=1;
St[i*2].mi=St[i*2+1].mi=val;
St[i*2].ma=St[i*2+1].ma=val;
}
return;
}
}
if (St[i].ty!=-1)
push(i);
int mid=(st+en)/2;
add(i*2,st,mid,l,r,val);add(i*2+1,mid+1,en,l,r,val);
St[i].mi=min(St[i*2].mi,St[i*2+1].mi);
St[i].ma=max(St[i*2].ma,St[i*2+1].ma);
}
void sub(int i,int st,int en,int l,int r,int val)
{
if (st>r||en<l)
return;
if (st>=l&&en<=r)
{
if (St[i].ma<=val)
return;
if (St[i].mi>=val)
{
St[i].mi=St[i].ma=val;
if (st!=en)
{
St[i*2].lazy=St[i*2+1].lazy=val;
St[i*2].ty=St[i*2+1].ty=2;
St[i*2].mi=St[i*2+1].mi=val;
St[i*2].ma=St[i*2+1].ma=val;
}
return;
}
}
if (St[i].ty!=-1)
push(i);
int mid=(st+en)/2;
sub(i*2,st,mid,l,r,val);sub(i*2+1,mid+1,en,l,r,val);
St[i].mi=min(St[i*2].mi,St[i*2+1].mi);
St[i].ma=max(St[i*2].ma,St[i*2+1].ma);
}
int get(int i,int r,int st,int en)
{
if (st==en)
return St[i].mi;
if (St[i].ty!=-1)
push(i);
int mid=(st+en)/2;
if (r<=mid)
return get(i*2,r,st,mid);
return get(i*2+1,r,mid+1,en);
}
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]);
else
sub(1,0,n-1,left[i],right[i],height[i]);
}
for (int i=0;i<n;i++)
finalHeight[i]=get(1,i,0,n-1);
}
