#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long long MAXN=2000009;
const long long inf=LLONG_MAX;
long long max1(long long a,long long b)
{
if(a>b)return a;
return b;
}
long long min1(long long a,long long b)
{
if(a<b)return a;
return b;
}
struct node
{
int l;
int r;
long long minLazy;
long long maxLazy;
void cons(int _l,int _r)
{
l=_l;
r=_r;
minLazy=0;
maxLazy=inf;
}
};
node tree[4*MAXN];
void build(int n,int l,int r)
{
tree[n].cons(l,r);
if(l==r)
{
return;
}
build(2*n,l,(l+r)/2);
build(2*n+1,(l+r)/2+1,r);
}
void push_lazy(int n)
{
if(tree[n].l==tree[n].r)return;
if(tree[n].minLazy>tree[2*n].maxLazy)
{
tree[2*n].minLazy=tree[n].minLazy;
tree[2*n].maxLazy=tree[n].minLazy;
}
else
{
tree[2*n].minLazy=max1(tree[2*n].minLazy,tree[n].minLazy);
}
if(tree[n].maxLazy<tree[2*n].minLazy)
{
tree[2*n].maxLazy=tree[n].maxLazy;
tree[2*n].minLazy=tree[n].maxLazy;
}
else
{
tree[2*n].maxLazy=min1(tree[2*n].maxLazy,tree[n].maxLazy);
}
if(tree[n].minLazy>tree[2*n+1].maxLazy)
{
tree[2*n+1].minLazy=tree[n].minLazy;
tree[2*n+1].maxLazy=tree[n].minLazy;
}
else
{
tree[2*n+1].minLazy=max1(tree[2*n+1].minLazy,tree[n].minLazy);
}
if(tree[n].maxLazy<tree[2*n+1].minLazy)
{
tree[2*n+1].maxLazy=tree[n].maxLazy;
tree[2*n+1].minLazy=tree[n].maxLazy;
}
else
{
tree[2*n+1].maxLazy=min1(tree[2*n+1].maxLazy,tree[n].maxLazy);
}
tree[n].minLazy=0;
tree[n].maxLazy=inf;
}
void addChange(int n,int l,int r,long long v)
{
push_lazy(n);
if(tree[n].l==l&&tree[n].r==r)
{
if(v>tree[n].maxLazy)
{
tree[n].minLazy=v;
tree[n].maxLazy=v;
}
else
{
tree[n].minLazy=max1(tree[n].minLazy,v);
}
return;
}
if(tree[2*n].r<l)
{
addChange(2*n+1,l,r,v);
return;
}
if(tree[2*n+1].l>r)
{
addChange(2*n,l,r,v);
return;
}
addChange(2*n,l,tree[2*n].r,v);
addChange(2*n+1,tree[2*n+1].l,r,v);
}
void remChange(int n,int l,int r,long long v)
{
push_lazy(n);
if(tree[n].l==l&&tree[n].r==r)
{
if(v<tree[n].minLazy)
{
tree[n].maxLazy=v;
tree[n].minLazy=v;
}
else
{
tree[n].maxLazy=min1(tree[n].maxLazy,v);
}
return;
}
if(tree[2*n].r<l)
{
remChange(2*n+1,l,r,v);
return;
}
if(tree[2*n+1].l>r)
{
remChange(2*n,l,r,v);
return;
}
remChange(2*n,l,tree[2*n].r,v);
remChange(2*n+1,tree[2*n+1].l,r,v);
}
long long getAns(int n,int t)
{
push_lazy(n);
if(tree[n].l==tree[n].r)
{
return tree[n].minLazy;
}
if(tree[2*n].r<t)
{
return getAns(2*n+1,t);
}
if(tree[2*n+1].l>t)
{
return getAns(2*n,t);
}
return -1;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
build(1,0,n-1);
for(int i=0;i<k;i++)
{
if(op[i]==1)
{
addChange(1,left[i],right[i],height[i]);
}
else
{
remChange(1,left[i],right[i],height[i]);
}
}
for(int i=0;i<n;i++)
{
finalHeight[i]=getAns(1,i);
}
}
