#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
int mini[8000002],maxi[8000000], lazymin[8000000],lazymax[8000000],fin[2000002];
bool ispmin[8000003], ispmax[8000003];
void add(int le,int ri,int l,int r,int h, int ind)
{
if(l<=le && ri<=r)
{
lazymax[ind]=max(lazymax[ind],h);ispmax[ind]=1;
}
if(ispmin[ind])
{
mini[ind]=min(mini[ind],lazymin[ind]);
maxi[ind]=min(maxi[ind],lazymin[ind]);
if(le!=ri)
{
lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
}
lazymin[ind]=100000000;ispmin[ind]=0;
}
if(ispmax[ind])
{
maxi[ind]=max(maxi[ind],lazymax[ind]);
mini[ind]=max(mini[ind],lazymax[ind]);
if(le!=ri)
{
lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);
ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
}
lazymax[ind]=0;ispmax[ind]=0;
}
if(l<=le && ri<=r)return;
if(l>ri || r<le)return;
int mid=(le+ri)/2;
add(le,mid,l,r,h,2*ind);
add(mid+1,ri,l,r,h,2*ind+1);
mini[ind]=min(mini[2*ind],mini[2*ind+1]);
maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);
}
void rem(int le,int ri,int l,int r,int h, int ind)
{
if(l<=le && ri<=r)
{
lazymin[ind]=min(lazymin[ind],h);
ispmin[ind]=1;
}
if(ispmax[ind])
{
maxi[ind]=max(maxi[ind],lazymax[ind]);
mini[ind]=max(mini[ind],lazymax[ind]);
if(le!=ri)
{
lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);
ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
}
lazymax[ind]=0;ispmax[ind]=0;
}
if(ispmin[ind])
{
mini[ind]=min(mini[ind],lazymin[ind]);
maxi[ind]=min(maxi[ind],lazymin[ind]);
if(le!=ri)
{
lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
}
lazymin[ind]=100000000;ispmin[ind]=0;
}
if(l<=le && ri<=r)return;
if(l>ri || r<le)return;
int mid=(le+ri)/2;
rem(le,mid,l,r,h,2*ind);
rem(mid+1,ri,l,r,h,2*ind+1);
mini[ind]=min(mini[2*ind],mini[2*ind+1]);
maxi[ind]=max(maxi[2*ind],maxi[2*ind+1]);
}
void query2(int le,int ri,int ind)
{
if(ispmin[ind])
{
mini[ind]=min(mini[ind],lazymin[ind]);
maxi[ind]=min(maxi[ind],lazymin[ind]);
if(le!=ri)
{
lazymin[2*ind]=min(lazymin[2*ind],lazymin[ind]);
lazymin[2*ind+1]=min(lazymin[2*ind+1],lazymin[ind]);
lazymax[2*ind]=min(lazymax[2*ind],lazymin[ind]);
lazymax[2*ind+1]=min(lazymax[2*ind+1],lazymin[ind]);
ispmin[2*ind]=ispmin[2*ind+1]=ispmax[2*ind]=ispmax[2*ind+1]=1;
}
lazymin[ind]=100000000;ispmin[ind]=0;
}
if(ispmax[ind])
{
maxi[ind]=max(maxi[ind],lazymax[ind]);
mini[ind]=max(mini[ind],lazymax[ind]);
if(le!=ri)
{
lazymax[2*ind]=max(lazymax[2*ind],lazymax[ind]);
lazymax[2*ind+1]=max(lazymax[2*ind+1],lazymax[ind]);
lazymin[2*ind]=max(lazymin[2*ind],lazymax[ind]);
lazymin[2*ind+1]=max(lazymin[2*ind+1],lazymax[ind]);
ispmax[2*ind]=ispmax[2*ind+1]=ispmin[2*ind]=ispmin[2*ind+1]=1;
}
lazymax[ind]=0;ispmax[ind]=0;
}
if(mini[ind]==maxi[ind])
{
for(int i=le;i<=ri;i++)fin[i]=mini[ind];
return;
}
if(le==ri){
return;
}
int mid=(le+ri)/2;
query2(le,mid,2*ind);
query2(mid+1,ri,2*ind+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
int i;
for(i=0;i<8000000;i++)lazymin[i]=100000000;
for(i=0;i<k;i++)
{
left[i]++;
right[i]++;
if(op[i]==1)add(1,n,left[i],right[i],height[i],1);
else rem(1,n,left[i],right[i],height[i],1);
}
query2(1,n,1);
for(i=0;i<n;i++)finalHeight[i]=fin[i+1];
return;
}
/*
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412
*/
