#include "wall.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
using namespace std;
const int mx=2e6+10;
const int inf=1e9+10;
pii tree[4*mx];
int curval[4*mx];
void merge(int par,int kid)
{
if(curval[par]!=-1)
{
curval[kid]=curval[par];
tree[kid]={inf,-1};
return;
}
if(curval[kid]!=-1)
{
if(curval[kid]<tree[par].s)
{
curval[kid]=tree[par].s;
}
else if(curval[kid]>tree[par].f)
{
curval[kid]=tree[par].f;
}
return;
}
tree[kid].f=min(tree[kid].f,tree[par].f);
tree[kid].s=max(tree[kid].s,tree[par].s);
if(tree[kid].f<=tree[kid].s)
{
if(tree[kid].f==tree[par].f)
{
curval[kid]=tree[kid].f;
}
else
{
curval[kid]=tree[kid].s;
}
tree[kid]={inf,-1};
return;
}
curval[kid]=-1;
}
int query(int node,int b,int e,int p)
{
if(curval[node]!=-1)
{
return curval[node];
}
if(b==e)
{
if(tree[node].s!=-1)return tree[node].s;
return 0;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
if(tree[node].f!=inf || tree[node].s!=-1)
{
merge(node,left);
merge(node,right);
}
if(p<=mid)return query(left,b,mid,p);
return query(right,mid+1,e,p);
}
void update(int node, int b,int e,int l,int r,int val,int type)
{
if(b>r||e<l)return;
if(b>=l && e<=r)
{
if(type==1)
{
if(curval[node]!=-1)
{
curval[node]=max(curval[node],val);
return;
}
if(val>tree[node].f)
{
curval[node]=val;
tree[node]={inf,-1};
return;
}
tree[node].s=max(tree[node].s,val);
curval[node]=-1;
}
else
{
if(curval[node]!=-1)
{
curval[node]=min(curval[node],val);
return;
}
if(val<tree[node].s)
{
curval[node]=val;
tree[node]={inf,-1};
return;
}
tree[node].f=min(tree[node].f,val);
curval[node]=-1;
}
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
merge(node,left);
merge(node,right);
tree[node]={inf,-1};
curval[node]=-1;
update(left,b,mid,l,r,val,type);
update(right,mid+1,e,l,r,val,type);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<k;i++)
{
int l=left[i]+1;
int r=right[i]+1;
int v=height[i];
update(1,1,n,l,r,v,op[i]);
}
for(int i=0;i<n;i++)finalHeight[i]=query(1,1,n,i+1);
return;
}
