#include "wall.h"
#include <iostream>
using namespace std;
long long int fh[10000005],mintree[10000005],maxtree[10000005],l,r,h;
int findtree(int s,int e,int t)
{
if(mintree[t]==maxtree[t])
{
for(int i=s;i<=e;i++)
{
fh[i]=mintree[t];
}
return 0;
}
findtree(s,(s+e)/2,t*2);
findtree((s+e)/2+1,e,t*2+1);
}
int add(int s,int e,int t)
{
//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
if(r<s || l>e)return 0;
if(l<=s && e<=r)
{
if(maxtree[t]<=h)
{
mintree[t]=h;
maxtree[t]=h;
return 0;
}
else if(mintree[t]>=h)return 0;
}
if(mintree[t]==maxtree[t])
{
maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
}
add(s,(s+e)/2,t*2);
add((s+e)/2+1,e,t*2+1);
mintree[t]=min(mintree[t*2],mintree[t*2+1]);
maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
int rem(int s,int e,int t)
{
//cout<<maxtree[t]<<" "<<mintree[t]<<" "<<s<<" "<<e<<endl;
if(r<s || l>e)return 0;
if(l<=s && e<=r)
{
if(mintree[t]>=h)
{
mintree[t]=h;
maxtree[t]=h;
return 0;
}
else if(maxtree[t]<=h)return 0;
}
if(mintree[t]==maxtree[t])
{
maxtree[t*2]=mintree[t*2]=maxtree[t*2+1]=mintree[t*2+1]=maxtree[t];
}
rem(s,(s+e)/2,t*2);
rem((s+e)/2+1,e,t*2+1);
mintree[t]=min(mintree[t*2],mintree[t*2+1]);
maxtree[t]=max(maxtree[t*2],maxtree[t*2+1]);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
for(int i=0;i<k;i++)
{
l=left[i],r=right[i],h=height[i];
if(op[i]==1)add(0,n-1,1);
else rem(0,n-1,1);
}
findtree(0,n-1,1);
for(int i=0;i<n;i++)
{
finalHeight[i]=fh[i];
//cout<<fh[i]<<" ";
}
//cout<<endl;
return;
}
