#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];
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]-1<=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]);//lazy1[node]=0;
lazy2[2*node]=min(lazy2[2*node],lazy2[node]);
lazy2[2*node+1]=min(lazy2[2*node+1],lazy2[node]);//lazy2[node]=1000000;
}
if((le<=y[l] && y[r]-1<=ri) || y[l]>ri || y[r]-1<le) return;
int mid=(l+r)/2;
update(2*node,l,mid,le,ri,type,h);
update(2*node+1,mid,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]);
}
if(l==r) 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];st[a[0]]=1;
int in=2;
for(int i=1;i<2*k;i++)
{
if(a[i]!=a[i-1])
{y[in]=a[i];st[a[i]]=in;in++;}
}
in--;
for(int i=1;i<=in;i++) lazy2[i]=1000000;
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 d;
for(int i=k-1;i>=0;i--)
{
d=left[i];
for(int p=left[i];p<=right[i];p++)
{
if(st[p]!=0) d=p;
// if(finalHeight[p] && finalHeight[y[st[p]+1]])
// {p=y[st[p]+1]-1;finalHeight[p]=1;continue;}
if(b[p]) continue;
b[p]=1;
if(op[i]==1) finalHeight[p]=lazy1[st[d]];
else {finalHeight[p]=lazy2[st[d]];}
}
}
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
*/
