#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define forw(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define getbit(mask,i) ((mask>>i)&1)
typedef long long int ll;
typedef pair<int,int> pii;
const ll maxN=2e6+5;
const ll mod=1e9+7;
const ll oo=1e9;
int ans[maxN];
struct segment
{
vector <int> mi,ma;
vector <pair<int,int>> lazy;
segment(int n)
{
mi.assign(4*n+5,oo);
ma.assign(4*n+5,-oo);
lazy.assign(4*n+5,{-oo,oo});
}
void maxi(int id, int h)
{
ma[id]=max(ma[id],h);
mi[id]=max(ma[id],h);
lazy[id].fi=max(lazy[id].fi,h);
lazy[id].se=max(lazy[id].se,h);
return;
}
void mini(int id, int h)
{
ma[id]=min(ma[id],h);
mi[id]=min(mi[id],h);
lazy[id].fi=min(lazy[id].fi,h);
lazy[id].se=min(lazy[id].se,h);
return;
}
void down(int id)
{
maxi(id*2,lazy[id].fi);
maxi(id*2+1,lazy[id].fi);
mini(id*2,lazy[id].se);
mini(id*2+1,lazy[id].se);
lazy[id]={-oo,+oo};
return;
}
void update(int id, int l, int r,int u, int v, int type, int h) // 1 : add, 2: remove
{
if (v<l || r<u) return;
if (u<=l && r<=v)
{
if (type==1) maxi(id,h);
else mini(id,h);
return;
}
down(id);
int mid=(l+r)/2;
update(id*2,l,mid,u,v,type,h);
update(id*2+1,mid+1,r,u,v,type,h);
ma[id]=ma[id*2];
mi[id]=mi[id*2];
maxi(id,ma[id*2+1]);
mini(id,mi[id*2+1]);
lazy[id]={-oo,oo};
return;
}
void get_ans(int id, int l, int r)
{
if (l==r)
{
if (ma[id]==-oo) ans[l]=0;
else ans[l]=ma[id];
return;
}
down(id);
int mid=(l+r)/2;
get_ans(id*2,l,mid);
get_ans(id*2+1,mid+1,r);
return;
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
segment seg(n);
forw(i,0,k-1)
seg.update(1,1,n,left[i]+1,right[i]+1,op[i],height[i]);
seg.get_ans(1,1,n);
forw(i,0,n-1)
finalHeight[i]=ans[i+1];
return;
}
