#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
ii segt[8000001],lazy[8000001];
int s,e,t,h;
ii imp(ii o,ii n)
{
if(o==mp(8000001*1LL,0*1LL))
return(n);
else if(n==mp(8000001*1LL,0*1LL))
return(o);
if(o.S<=n.F)
return(mp(n.F,n.F));
if(o.S>=n.F&&o.F<=n.F&&n.S>=o.S)
return(mp(n.F,o.S));
if(n.F>=o.F&&n.S<=o.S)
return(n);
if(o.F>=n.F&&o.S<=n.S)
return(o);
if(o.F>=n.F&&o.S>=n.S&&n.S>=o.F)
return(mp(o.F,n.S));
if(o.F>=n.S)
return(mp(n.S,n.S));
}
void up(int node,int l,int r)
{
if(lazy[node]!=mp(8000001*1LL,0*1LL))
{
segt[node]=imp(segt[node],lazy[node]);
lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
lazy[node]=mp(8000001*1LL,0*1LL);
}
if(l>e||r<s)
return;
if(l>=s&&r<=e)
{
segt[node]=imp(segt[node],(t==1)?(mp(h,1000000)):(mp(0,h)));
lazy[2*node+1]=imp(lazy[2*node+1],(t==1)?(mp(h,1000000)):(mp(0,h)));
lazy[2*node+2]=imp(lazy[2*node+2],(t==1)?(mp(h,1000000)):(mp(0,h)));
return;
}
int m=(l+r)/2;
up(2*node+1,l,m);
up(2*node+2,m+1,r);
segt[node]=mp(min(segt[2*node+1].F,segt[2*node+2].F),max(segt[2*node+1].S,segt[2*node+2].S));
}
ii qu(int node,int l,int r)
{
if(lazy[node]!=mp(8000001*1LL,0*1LL))
{
segt[node]=imp(segt[node],lazy[node]);
lazy[2*node+1]=imp(lazy[2*node+1],lazy[node]);
lazy[2*node+2]=imp(lazy[2*node+2],lazy[node]);
lazy[node]=mp(8000001,0);
}
if(l>e||r<s)
return(mp(8000001,0));
if(l>=s&&r<=e)
{
return(segt[node]);
}
int m=(l+r)/2;
ii q1=qu(2*node+1,l,m),q2=qu(2*node+2,m+1,r);
return(mp(min(q1.F,q2.F),max(q1.S,q2.S)));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
for(int i=0;i<8000001;++i)
{
lazy[i]=mp(8000001,0);
segt[i]=mp(8000001,0);
}
for(int i=0;i<k;++i)
{
t=op[i];s=left[i],e=right[i],h=height[i];
up(0,0,n-1);
}
for(int i=0;i<n;++i)
{
s=i;e=i;
finalHeight[i]=(qu(0,0,n-1)).F;
if(finalHeight[i]==8000001)
finalHeight[i]=0;
}
return;
}
