#include "wall.h"
#include <iostream>
using namespace std;
int maxim[4500005];
int minim[4500005];
int rez[2000005];
int lazy[4500005];
void build(int node,int st,int dr)
{
minim[node]=0;
maxim[node]=0;
lazy[node]=-1;
if(st!=dr)
{
int mij=(st+dr)/2;
build(node*2,st,mij);
build(node*2+1,mij+1,dr);
}
}
void push(int node,int st,int dr)
{
if(lazy[node]!=-1)
{
minim[node]=lazy[node];
maxim[node]=lazy[node];
if(st!=dr)
{
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
}
lazy[node]=-1;
}
}
void dfs(int node,int st,int dr)
{
push(node,st,dr);
if(st!=dr)
{
int mij=(st+dr)/2;
dfs(node*2,st,mij);
dfs(node*2+1,mij+1,dr);
}
else
{
rez[st]=maxim[node];
}
}
void update(int node,int st,int dr,int qst,int qdr,int val,int tip)
{
push(node,st,dr);
if(st>dr || st>qdr || qst>dr || qst>qdr)
{
return;
}
if(qst<=st && dr<=qdr)
{
if(val>=maxim[node] || val<=minim[node])
{
if(val>=maxim[node] && tip==1)
{
lazy[node]=val;
push(node,st,dr);
return;
}
if(val<=minim[node] && tip==0)
{
lazy[node]=val;
push(node,st,dr);
return;
}
return;
}
else
{
int mij=(st+dr)/2;
update(node*2,st,mij,qst,qdr,val,tip);
update(node*2+1,mij+1,dr,qst,qdr,val,tip);
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
minim[node]=min(minim[node*2],minim[node*2+1]);
return;
}
}
int mij=(st+dr)/2;
update(node*2,st,mij,qst,qdr,val,tip);
update(node*2+1,mij+1,dr,qst,qdr,val,tip);
maxim[node]=max(maxim[node*2],maxim[node*2+1]);
minim[node]=min(minim[node*2],minim[node*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
build(1,1,n);
for(int i=0;i<k;i++)
{
if(op[i]==2)
{
op[i]=0;
}
update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
}
dfs(1,1,n);
for(int i=1;i<=n;i++)
{
finalHeight[i-1]=rez[i];
}
return;
}
