#include "data_structure/li_chao_tree.hpp"
#pragma once #include<limits> #include<cmath> #include<algorithm> /** * @brief LiChaoTree */ template<typename T> class LHT{ using lint = long long; struct node; using np = node*; struct node{ T a,b; np ch[2]={nullptr,nullptr}; node(T a,T b):a(a),b(b){} }; np root=nullptr; T sign(T x){return (x>0)-(x<0);} np update(T a,T b,lint p,lint q,lint l,lint r,np t){ if(!t)t=new node(0,std::numeric_limits<T>::max()); //区間外 if(r<=p||q<=l)return t; //全て区間内 if(p<=l&&r<=q){ lint m=(l+r)/2; if(a*m+b<=(t->a)*m+(t->b)){ std::swap(a,t->a); std::swap(b,t->b); } if(r-l==1||a==t->a)return t; if(sign((a-t->a)*l+(b-t->b))*sign((a-t->a)*m+(b-t->b))<=0)t->ch[0]=update(a,b,p,q,l,m,t->ch[0]); if(sign((a-t->a)*m+(b-t->b))*sign((a-t->a)*r+(b-t->b))<=0)t->ch[1]=update(a,b,p,q,m,r,t->ch[1]); return t; } //一部区間内 t->ch[0]=update(a,b,p,q,l,(l+r)/2,t->ch[0]); t->ch[1]=update(a,b,p,q,(l+r)/2,r,t->ch[1]); return t; } T get(lint x,lint l,lint r,np t){ if(!t)return std::numeric_limits<T>::max(); if(r-l==1)return t->a*x+t->b; lint m=(l+r)/2; if(l<=x&&x<m)return std::min(t->a*x+t->b,get(x,l,m,t->ch[0])); else return std::min(t->a*x+t->b,get(x,m,r,t->ch[1])); } lint mn; lint mx; public: LHT(lint mn=-1LL<<30,lint mx=1LL<<30):mn(mn),mx(mx){} T get(lint x){ return get(x,mn,mx,root); } void add_line(T a,T b){ root=update(a,b,mn,mx,mn,mx,root); } void add_segment(lint l,lint r,T a,T b){ root=update(a,b,l,r,mn,mx,root); } };
#line 2 "data_structure/li_chao_tree.hpp" #include<limits> #include<cmath> #include<algorithm> /** * @brief LiChaoTree */ template<typename T> class LHT{ using lint = long long; struct node; using np = node*; struct node{ T a,b; np ch[2]={nullptr,nullptr}; node(T a,T b):a(a),b(b){} }; np root=nullptr; T sign(T x){return (x>0)-(x<0);} np update(T a,T b,lint p,lint q,lint l,lint r,np t){ if(!t)t=new node(0,std::numeric_limits<T>::max()); //区間外 if(r<=p||q<=l)return t; //全て区間内 if(p<=l&&r<=q){ lint m=(l+r)/2; if(a*m+b<=(t->a)*m+(t->b)){ std::swap(a,t->a); std::swap(b,t->b); } if(r-l==1||a==t->a)return t; if(sign((a-t->a)*l+(b-t->b))*sign((a-t->a)*m+(b-t->b))<=0)t->ch[0]=update(a,b,p,q,l,m,t->ch[0]); if(sign((a-t->a)*m+(b-t->b))*sign((a-t->a)*r+(b-t->b))<=0)t->ch[1]=update(a,b,p,q,m,r,t->ch[1]); return t; } //一部区間内 t->ch[0]=update(a,b,p,q,l,(l+r)/2,t->ch[0]); t->ch[1]=update(a,b,p,q,(l+r)/2,r,t->ch[1]); return t; } T get(lint x,lint l,lint r,np t){ if(!t)return std::numeric_limits<T>::max(); if(r-l==1)return t->a*x+t->b; lint m=(l+r)/2; if(l<=x&&x<m)return std::min(t->a*x+t->b,get(x,l,m,t->ch[0])); else return std::min(t->a*x+t->b,get(x,m,r,t->ch[1])); } lint mn; lint mx; public: LHT(lint mn=-1LL<<30,lint mx=1LL<<30):mn(mn),mx(mx){} T get(lint x){ return get(x,mn,mx,root); } void add_line(T a,T b){ root=update(a,b,mn,mx,mn,mx,root); } void add_segment(lint l,lint r,T a,T b){ root=update(a,b,l,r,mn,mx,root); } };