Convex Hull Trick

// N本のy=ax+bがあったとき。
// xについて最も最小or最大のyをO(logN)で求めることができます。

// 最小値
struct ConvexHullTrick {
  deque<pair<ll, ll> > lines;

  ll check(pair<ll, ll> l1, pair<ll, ll> l2, pair<ll, ll> l3) {
    if (l1 < l3) swap(l1, l3);
    if ((l3.se - l2.se) * (l2.fi - l1.fi) >= (l2.se - l1.se) * (l3.fi - l2.fi)) {
      return 1;
    }
    return 0;
  }

  // y = ax + b
  void add(ll a, ll b) {
    pair<ll, ll> l(a, b);
    while (lines.size() >= 2 && check(*(lines.end() - 2), *(lines.end() - 1), l)) {
      lines.pop_back();
    }
    lines.push_back(l);
  }

  ll f(pair<ll, ll> l, ll x) {
    return l.fi * x + l.se;
  }

  ll getmin(ll x) {
    ll low = -1, high = lines.size() - 1;
    while (high - low > 1) {
      ll m = (low + high) / 2;
      if(f(lines[m], x) > f(lines[m + 1], x)){
        low = m;
      }
      else{
        high = m;
      }
    }
    return f(lines[high], x);
  }
} cht;

// 最大値
struct ConvexHullTrick {
  deque<pair<ll, ll> > lines;

  ll check(pair<ll, ll> l1, pair<ll, ll> l2, pair<ll, ll> l3) {
    if (l1 < l3) swap(l1, l3);
    if ((l3.se - l2.se) * (l2.fi - l1.fi) >= (l2.se - l1.se) * (l3.fi - l2.fi)) {
      return 1;
    }
    return 0;
  }

  // y = ax + b
  void add(ll a, ll b) {
    pair<ll, ll> l(a, b);
    while (lines.size() >= 2 && check(*(lines.end() - 2), *(lines.end() - 1), l)) {
      lines.pop_back();
    }
    lines.push_back(l);
  }

  ll f(pair<ll, ll> l, ll x) {
    return l.fi * x + l.se;
  }

  ll getmax(ll x) {
    static ll m = 0;
    while (lines.size()-m >= 2 && (f(lines[m], x) > f(lines[m + 1], x))) {
      m++;
    }
    return f(lines[m], x);
  }
} cht;