#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
struct segment_tree
{
struct node
{
long long mx,mn,left,right;
};
long long inf=1e18;
node dum;
vector<node>tree;
vector<long long>upd_mn,upd_mx;
node operation(node x,node z)
{
node ret;
ret.mx=max(x.mx,z.mx);
ret.mn=min(x.mn,z.mn);
ret.left=min(x.left,z.left);
ret.right=max(x.right,z.right);
return ret;
}
void push(long node)
{
if(upd_mn[node]!=inf){
tree[node].mx=min(tree[node].mx,upd_mn[node]);
tree[node].mn=min(tree[node].mn,tree[node].mx);
if(node<tree[0].mx){
upd_mn[node*2]=upd_mn[node];
upd_mn[node*2+1]=upd_mn[node];
}
upd_mn[node]=inf;
}
if(upd_mx[node]!=-inf){
tree[node].mn=max(tree[node].mn,upd_mx[node]);
tree[node].mx=max(tree[node].mn,tree[node].mx);
if(node<tree[0].mx){
upd_mx[node*2]=upd_mx[node];
upd_mx[node*2+1]=upd_mx[node];
}
upd_mx[node]=-inf;
}
}
void build(vector<long long>v)
{
tree.clear();
upd_mn.clear();
upd_mx.clear();
long long x=((v.size())*2)-1;
while(x&(x-1)){
x=x&(x-1);
}
tree.resize(x*2);
upd_mn.resize(x*2);
upd_mx.resize(x*2);
tree[0].mx=x;
dum.mx=0;
dum.mn=0;
dum.left=-1e18;
dum.right=1e18;
for(long i=0;i<v.size();i++){
upd_mn[i]=inf;
upd_mx[i]=-inf;
tree[i+x].mx=v[i];
tree[i+x].mn=v[i];
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=v.size();i<x;i++){
upd_mn[i]=inf;
upd_mx[i]=-inf;
tree[i+x].left=i;
tree[i+x].right=i;
}
for(long i=x-1;i>0;i--){
upd_mn[i]=inf;
upd_mx[i]=-inf;
tree[i]=operation(tree[i*2],tree[(i*2)+1]);
}
}
node get(long long l,long long r,long node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return dum;
}
if(tree[node].left>=l&&tree[node].right<=r){
return tree[node];
}
return operation(get(l,r,node*2),get(l,r,(node*2)+1));
}
void update_mx(long long l,long long r,long long z,long long node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return;
}
if(tree[node].left>=l&&tree[node].right<=r){
tree[node].mn=max(tree[node].mn,z);
tree[node].mx=max(tree[node].mn,tree[node].mx);
if(node<tree[0].mx){
upd_mx[node*2]=max(z,upd_mx[node*2]);
upd_mn[node*2]=max(z,upd_mn[node*2]);
upd_mx[node*2+1]=max(z,upd_mx[node*2+1]);
upd_mn[node*2+1]=max(z,upd_mn[node*2+1]);
}
return;
}
update_mx(l,r,z,node*2);
update_mx(l,r,z,(node*2)+1);
tree[node]=operation(tree[node*2],tree[(node*2)+1]);
}
void update_mn(long long l,long long r,long long z,long long node=1)
{
push(node);
if(tree[node].left>r||tree[node].right<l){
return;
}
if(tree[node].left>=l&&tree[node].right<=r){
tree[node].mx=min(tree[node].mx,z);
tree[node].mn=min(tree[node].mn,tree[node].mx);
if(node<tree[0].mx){
upd_mn[node*2]=min(z,upd_mn[node*2]);
upd_mx[node*2]=min(z,upd_mx[node*2]);
upd_mn[node*2+1]=min(z,upd_mn[node*2+1]);
upd_mx[node*2+1]=min(z,upd_mx[node*2+1]);
}
return;
}
update_mn(l,r,z,node*2);
update_mn(l,r,z,(node*2)+1);
tree[node]=operation(tree[node*2],tree[(node*2)+1]);
}
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
vector<long long>dum(n);
segment_tree st;
st.build(dum);
for(int i=0;i<k;i++){
if(op[i]==1){
st.update_mx(left[i],right[i],height[i]);
continue;
}
st.update_mn(left[i],right[i],height[i]);
}
for(int i=0;i<n;i++){
finalHeight[i]=st.get(i,i).mx;
}
return;
}
