#include<bits/stdc++.h>
#include "wall.h"
#define fi first
#define se second
using namespace std;
const int N=2e6,K=5e5,MN=0,MX=1e5;
const int P=21e5;
int pot;
pair<int,int> tree[2*P+10];
void merge(pair<int,int> &x,pair<int,int> y)
{
if(y.se<x.fi)
x={y.se,y.se};
else if(x.se<y.fi)
x={y.fi,y.fi};
else
{
x.fi=max(x.fi,y.fi);
x.se=min(x.se,y.se);
}
return;
}
void push_down(int i)
{
merge(tree[2*i],tree[i]);
merge(tree[2*i+1],tree[i]);
tree[i]={MN,MX};
return;
}
void add_t(int i,int l,int r,int ls,int rs,pair<int,int> c)
{
if(r<ls || rs<l)
return;
else if(ls<=l && r<=rs)
{
merge(tree[i],c);
return;
}
push_down(i);
int mid=(l+r)/2;
add_t(2*i,l,mid,ls,rs,c);
add_t(2*i+1,mid+1,r,ls,rs,c);
return;
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
for(pot=1;pot<n;pot*=2);
for(int i=1;i<=2*pot;i++)
tree[i]={MN,MX};
for(int i=0;i<k;i++)
{
if(op[i]==1) // adding phase
add_t(1,1,pot,left[i]+1,right[i]+1,{height[i],MX});
else // removing phase
add_t(1,1,pot,left[i]+1,right[i]+1,{MN,height[i]});
}
for(int i=1;i<pot;i++)
push_down(i);
for(int i=0;i<n;i++)
finalHeight[i]=tree[i+pot].fi;
return;
}
