#include using namespace std; #define int long long #define rep(i,n) for(int i=0;i<(n);i++) #define pb push_back #define all(v) (v).begin(),(v).end() #define fi first #define se second typedef vectorvint; typedef pairpint; typedef vectorvpint; templateinline void chmin(A &a,B b){if(a>b)a=b;} templateinline void chmax(A &a,B b){if(a ostream& operator<<(ostream& ost,const pair&p){ ost<<"{"< ostream& operator<<(ostream& ost,const vector&v){ ost<<"{"; for(int i=0;i struct ConvexHullTrick{ #define a first #define b second using Line=pair; dequelines; //l.a>=m.a>=r.a inline bool notNecessary(const Line &l,const Line &m,const Line &r){ return (m.a-l.a)*(r.b-m.b)>=(m.b-l.b)*(r.a-m.a); } void addLine(I a,I b){ if(!isMin)a*=-1,b*=-1; Line l(a,b); if(lines.empty())lines.push_back(l); else if(lines.front().a<=a){ if(lines.front().a==a){ if(lines.front().b<=b)return; lines.pop_front(); } while(lines.size()>=2&¬Necessary(l,lines[0],lines[1]))lines.pop_front(); lines.push_front(l); } else{ if(lines.back().a==a){ if(lines.back().b<=b)return; lines.pop_back(); } while(lines.size()>=2&¬Necessary(lines[lines.size()-2],lines[lines.size()-1],l))lines.pop_back(); lines.push_back(l); } } inline I eval(const Line &l,I x){ return l.a*x+l.b; } I query(I x){ int lb=-1,ub=lines.size()-1; while(ub-lb>1){ int mid=(ub+lb)/2; if(eval(lines[mid],x)<=eval(lines[mid+1],x))ub=mid; else lb=mid; } if(isMin)return eval(lines[ub],x); return -eval(lines[ub],x); } I queryMonotoneInc(I x){ while(lines.size()>=2&&eval(lines[0],x)>=eval(lines[1],x))lines.pop_front(); if(isMin)return eval(lines[0],x); return -eval(lines[0],x); } I queryMonotoneDec(I x){ while(lines.size()>=2&&eval(lines[lines.size()-1],x)>=eval(lines[lines.size()-2],x))lines.pop_back(); if(isMin)return eval(lines.back(),x); return -eval(lines.back(),x); } #undef a #undef b }; struct UnionFindTree{ vectorpar,sz; UnionFindTree(int n=0){ par.resize(n); sz.resize(n); for(int i=0;i