#include<iostream>
#include<cstring>
#include<algorithm>
#include "wall.h"
using namespace std;
int a[1000005],y[1000005],tree[4000005],mi[4000005],ma[4000005],st[1000005],re[1000005];
int lazy1[4000005],lazy2[4000005];
bool b[1000005];
void update(int node,int l,int r,int le,int ri,int type,int h)
{
if(le<=y[l] && y[r]<=ri)
{
if(type==1)
lazy1[node]=max(lazy1[node],h);
else lazy2[node]=min(lazy2[node],h);
}
if(l!=r)
{
lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);
lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);
}
if((le<=y[l] && y[r]<=ri) || y[l]>ri || y[r]<le) return;
int mid=(l+r)/2;
update(2*node,l,mid,le,ri,type,h);
update(2*node+1,mid+1,r,le,ri,type,h);
}
void updatefinal(int node,int l,int r)
{
if(l!=r)
{
lazy1[2*node]=max(lazy1[2*node],lazy1[node]);
lazy1[2*node+1]=max(lazy1[2*node+1],lazy1[node]);
lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);
lazy1[2*node]=min(lazy1[2*node],lazy2[node]);
lazy2[2*node]=max(lazy2[2*node],lazy1[node]);
lazy1[2*node+1]=min(lazy1[2*node+1],lazy2[node]);
lazy2[2*node+1]=max(lazy2[2*node+1],lazy1[node]);
lazy1[node]=-1;
lazy2[node]=1000000;
}
if(l==r) {re[y[l]]=lazy1[node];return;}
int mid=(l+r)/2;
updatefinal(2*node,l,mid);
updatefinal(2*node+1,mid+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<k;i++)
{
a[2*i]=left[i];
a[2*i+1]=right[i];
}
sort(a,a+2*k);
y[1]=a[0];
int in=2;
for(int i=1;i<2*k;i++)
{
if(a[i]!=a[i-1])
{y[in]=a[i];in++;}
}
in--;
for(int i=1;i<=in;i++) {lazy2[i]=1000000;lazy1[i]=-1;}
for(int i=0;i<k;i++)
{
if(op[i]==1) //adding
{
update(1,1,in,left[i],right[i],1,height[i]);
}
else //removing
{
update(1,1,in,left[i],right[i],2,height[i]);
}
}
updatefinal(1,1,in);
int p=0,z=1;
for(int i=0;i<n;i++)
{
if(y[z]==i) {p=i;z++;}
finalHeight[i]=re[p];
}
return;
}
/*
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0
*/
