#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define ll int
ll n;
pair<ll,ll>f[8000006];
bool laz[8000006];
pair<ll,ll>collab(pair<ll,ll>a,pair<ll,ll>b)
{
pair<ll,ll>c;
c={max(a.first,b.first),min(a.second,b.second)};
if(c.first>c.second)
{
if(a.first<b.first)
return {c.first,c.first};
return {c.second,c.second};
}
return c;
}
void update(ll id,ll l,ll r,ll u,ll v,ll w,ll type)
{
if(l>v||r<u)return;
if(l>=u&&r<=v)
{
if(type==1)
f[id]=collab(f[id],{w,1e9});
else
f[id]=collab(f[id],{0,w});
return;
}
ll mid=(l+r)/2;
f[id*2]=collab(f[id*2],f[id]);
f[id*2+1]=collab(f[id*2+1],f[id]);
f[id]={0,1e9};
update(id*2,l,mid,u,v,w,type);
update(id*2+1,mid+1,r,u,v,w,type);
}
ll getans(ll id,ll l,ll r,ll u)
{
if(l>u||r<u)
return 0;
if(l==r)
return f[id].first;
ll mid=(l+r)/2;
f[id*2]=collab(f[id*2],f[id]);
f[id*2+1]=collab(f[id*2+1],f[id]);
f[id]={0,1e9};
return getans(id*2,l,mid,u)+getans(id*2+1,mid+1,r,u);
}
void build(ll id,ll l,ll r)
{
f[id]={0,1e9};
if(l==r)
{
f[id]={0,0};
return;
}
ll mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void buildWall(int N,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
n=N;
build(1,1,n);
for(int i=0;i<k;i++)
update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
for(int i=0;i<n;i++)
finalHeight[i]=getans(1,1,n,i+1);
return ;
}
