Convex Hull Trick (C++)

目的

直線の集合{$f_i(x)=a_ix+b_i$}に対して、「直線の追加」と「ある数$x'$に対して最小値$\min_i{f_i(x')}$を求める」の2種類のクエリをならし$O(1)$で求めます。ただし、追加される直線の傾きは単調減少かつ$x'$はクエリの順番に対して単調増加でなければなりません。

計算量

ならし$O(1)$

使い方

void add(long long a, long long b)
傾き$a$、切片$b$の直線を追加します。
long long query(long long x)
$\min_i{f_i(x)}$をreturn

ソースコード

#include <bits/stdc++.h>

//傾きは単調減少

struct ConvexHullTrick{
  std::deque<std::pair<long long, long long> > dq; //(傾き、切片)

  void add(long long a, long long b){
    std::pair<long long, long long> p0=std::make_pair(a, b);
    while(dq.size()>=2){
      int sz=dq.size();
      std::pair<long long, long long> p1=dq[sz-1];
      std::pair<long long, long long> p2=dq[sz-2];
      if((p0.second-p1.second)*(p0.first-p2.first) < (p0.second-p2.second)*(p0.first-p1.first))break;//交点のx座標を比較
      dq.pop_back();
    }
    dq.push_back(p0);
  }

  long long query(long long x){
    while(dq.size()>=2){
      long long v1=dq[0].first*x+dq[0].second;
      long long v2=dq[1].first*x+dq[1].second;
      if(v1<=v2)break;
      dq.pop_front();
    }
    return dq[0].first*x+dq[0].second;
  }

};

Verified

Educational DP Contest / Z