#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>
#include "wall.h"
namespace segment_tree {
enum class query_type {UPD, SET, NONE};
template<typename T> struct query {query_type q=query_type::NONE; T v;};
template<typename T> struct node {T v; int64_t parent{-1}; int64_t l_child{-1}; int64_t r_child{-1}; int64_t len{1}; query<T> q;};
template<typename T,class comb,class upd=comb>
class lazy_tree {
public:
// i'm so happy i can do this
lazy_tree(int64_t n_=0,comb f_=comb(),upd g_=upd()):f(f_),g(g_),n(n_) {
seg.resize(2*n);
for(int64_t i=1;i<n;++i) {
seg[i].parent=i/2;
seg[i].l_child=2*i;
seg[i].r_child=2*i+1;
}
seg[0].l_child=1;
for(int64_t i=n;i<2*n;++i) {seg[i].parent=i/2;}
for(int64_t i=n-1;i>=1;--i) {
seg[i].len=seg[seg[i].l_child].len+seg[seg[i].r_child].len;
}
for(int64_t i=0;i<2*n;++i) {seg[i].v=id; seg[i].q.v=id;}
}
void update(int64_t a,int64_t b,T v) {__update_r_(0,n-1,seg[0].l_child,a,b,{query_type::UPD,v});}
void set(int64_t a,int64_t b,T v) {__update_r_(0,n-1,seg[0].l_child,a,b,{query_type::SET,v});}
T range_query(int64_t a,int64_t b) {return __query_r_(a,b,seg[0].l_child,0,n-1);}
std::vector<node<T>> full_tree() {return seg;}
private:
// we assume that f and g share the same identity, otherwise we're a bit cooked
comb f; upd g; int64_t n{0}; const T id{f.id};
std::vector<node<T>> seg;
void __apply_(int64_t ptr,const query<T> &x) {
if(x.q==query_type::UPD) {
if(seg[ptr].q.q!=query_type::SET) {
seg[ptr].q=query<T>({query_type::UPD,g(seg[ptr].q.v,x.v)});
} else {
seg[ptr].q=query<T>({query_type::SET,g(seg[ptr].q.v,x.v)});
}
seg[ptr].v=g(seg[ptr].v,x.v,seg[ptr].len);
} else if(x.q==query_type::SET) {
seg[ptr].v=g(id,x.v,seg[ptr].len);
seg[ptr].q=x;
} else {}
}
void __push_down_(int64_t ptr) {
if(seg[ptr].l_child!=-1) {
__apply_(seg[ptr].l_child,seg[ptr].q);
__apply_(seg[ptr].r_child,seg[ptr].q);
} else {}
seg[ptr].q=query<T>();
seg[ptr].q.v=id;
}
void __update_r_(int64_t l,int64_t r,int64_t k,int64_t ql,int64_t qr,const query<T> &x) {
if(qr<l||ql>r) {return;}
if(ql<=l&&r<=qr) {
__apply_(k,x);
} else {
__push_down_(k);
int m=l+seg[seg[k].l_child].len-1;
__update_r_(l,m,seg[k].l_child,ql,qr,x);
__update_r_(m+1,r,seg[k].r_child,ql,qr,x);
seg[k].v=f(seg[seg[k].l_child].v,seg[seg[k].r_child].v);
}
}
T __query_r_(int64_t a,int64_t b,int64_t k,int64_t x,int64_t y) {
if(b<x||a>y) {return id;}
if(a<=x&&y<=b) {return seg[k].v;}
__push_down_(k);
int d=x+seg[seg[k].l_child].len-1;
return f(__query_r_(a,b,seg[k].l_child,x,d),__query_r_(a,b,seg[k].r_child,d+1,y));
}
};
};
template<typename T> using pmmx=std::pair<T,T>;
// here, we represent a modification as f_{a,b}(x)=min(max(x,a),b); setting elements to c also corresponds to such an operation; in this case we let a=b=c.
template<typename T>
class minmax {
public:
pmmx<T> operator()(pmmx<T> a,pmmx<T> b,int k=1) {
if(a.first>a.second) {a.first=a.second;}
if(b.first>b.second) {b.first=b.second;}
if(a.first<=b.first&&b.first<=a.second&&a.second<=b.second) {
return {b.first,a.second};
} else if(b.first<=a.first&&a.first<=b.second&&b.second<=a.second) {
return {a.first,b.second};
} else if(a.first<=b.first&&b.first<=b.second&&b.second<=a.second) {
return b;
} else if(b.first<=a.first&&a.first<=a.second&&a.second<=b.second) {
return a;
} else if(b.first<=b.second&&b.second<=a.first&&a.first<=a.second) {
return {b.second,b.second};
} else if(a.first<=a.second&&a.second<=b.first&&b.first<=b.second) {
return {b.first,b.first};
} else {
return {0,0};
}
}
const pmmx<T> id{pmmx{std::numeric_limits<T>::min(),std::numeric_limits<T>::max()}};
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
segment_tree::lazy_tree<pmmx<int>,minmax<int>> segtree(n);
for(int i=0;i<k;++i) {
if(op[i]==1) {
segtree.update(left[i],right[i],{height[i],std::numeric_limits<int>::max()});
} else {
segtree.update(left[i],right[i],{std::numeric_limits<int>::min(),height[i]});
}
}
pmmx<int> func;
for(int i=0;i<n;++i) {
func=segtree.range_query(i,i);
finalHeight[i]=std::min(std::max(0,func.first),func.second);
}
}
