test/yj_line_add_get_min_li_chao_tree.test.cpp

#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <map>
#include <tuple>
#include <vector>

#include "DataStructure/li_chao_tree.cpp"

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  std::vector<std::tuple<int, intmax_t, intmax_t>> qs;
  qs.reserve(n+q);
  std::map<intmax_t, size_t> enc;
  for (size_t i = 0; i < n; ++i) {
    intmax_t a, b;
    scanf("%jd %jd", &a, &b);
    qs.emplace_back(0, a, b);
  }
  for (size_t i = 0; i < q; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 0) {
      intmax_t a, b;
      scanf("%jd %jd", &a, &b);
      qs.emplace_back(0, a, b);
    } else if (t == 1) {
      intmax_t p;
      scanf("%jd", &p);
      enc[p];
      qs.emplace_back(1, p, 0);
    }
  }

  size_t m = 0;
  std::vector<intmax_t> xs;
  xs.reserve(enc.size());
  for (auto& [d, e]: enc) xs.push_back(d), e = m++;

  lower_linear_envelope<intmax_t, li_chao_tree_tag> lle(xs.begin(), xs.end());
  for (auto [t, a, b]: qs) {
    if (t == 0) {
      lle.push(a, b);
    } else if (t == 1) {
      intmax_t y = lle.get_nth(enc.at(a));
      printf("%jd\n", y);
    }
  }
}

#line 1 "test/yj_line_add_get_min_li_chao_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/line_add_get_min"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <map>
#include <tuple>
#include <vector>

#line 1 "DataStructure/li_chao_tree.cpp"



/**
 * @brief Li-Chao tree
 * @author えびちゃん
 */

#include <cstddef>
#line 11 "DataStructure/li_chao_tree.cpp"
#include <utility>
#line 13 "DataStructure/li_chao_tree.cpp"

#line 1 "utility/limits.cpp"



/**
 * @brief 型依存の定数
 * @author えびちゃん
 */

#include <limits>
#line 11 "utility/limits.cpp"

template <typename Tp>
class limits: public std::numeric_limits<Tp> {};

template <typename T1, typename T2>
class limits<std::pair<T1, T2>> {
public:
  static constexpr auto min() {
    return std::make_pair(limits<T1>::min(), limits<T2>::min());
  }
  static constexpr auto max() {
    return std::make_pair(limits<T1>::max(), limits<T2>::max());
  }
};


#line 15 "DataStructure/li_chao_tree.cpp"

template <typename Tp, typename Tag>
class lower_linear_envelope;

struct li_chao_tree_tag {};

template <typename Tp>
class lower_linear_envelope<Tp, li_chao_tree_tag> {
public:
  using value_type = Tp;
  using size_type = size_t;

private:
  std::vector<value_type> M_x;
  std::vector<value_type> M_a, M_b;

  // FIXME: use fused_mul_add_min(a, x, b, y)

  void M_descend(size_type i, value_type a, value_type b) {
    size_type n = M_x.size();
    size_type l = i, r = l+1;
    while (l < n) l <<= 1, r <<= 1;

    while (l < r) {
      size_type m = (l+r) >> 1;
      value_type xl = M_x[l-n], xm = M_x[m-n], xr = M_x[r-1-n];
      value_type a0 = M_a[i], b0 = M_b[i];
      value_type yl0 = a0*xl+b0, ym0 = a0*xm+b0, yr0 = a0*xr+b0;
      value_type yl = a*xl+b, ym = a*xm+b, yr = a*xr+b;
      if (yl0 < yl && yr0 < yr) return;
      if (yl < yl0 && yr < yr0) {
        M_a[i] = a, M_b[i] = b;
        return;
      }

      if (ym < ym0) {
        std::swap(M_a[i], a);
        std::swap(M_b[i], b);
      }
      if ((yl0 < yl && yr < yr0) ^ (ym < ym0)) {
        l = m;
        (i <<= 1) |= 1;
      } else {
        r = m;
        i <<= 1;
      }
    }
  }

public:
  lower_linear_envelope() = default;

  template <typename InputIt>
  lower_linear_envelope(InputIt first, InputIt last):
    M_x(first, last),
    M_a(2*M_x.size(), 0), M_b(2*M_x.size(), limits<value_type>::max())
  {}

  void push(value_type a, value_type b) { push(a, b, 0, M_x.size()); }
  void push(value_type a, value_type b, size_type l, size_type r) {
    size_type n = M_x.size();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) M_descend(l++, a, b);
      if (r & 1) M_descend(--r, a, b);
    }
  }

  value_type get_nth(size_type i) const {
    size_type n = M_x.size();
    value_type x = M_x[i];
    value_type y = limits<value_type>::max();
    i += n;
    while (i > 0) {
      value_type a = M_a[i], b = M_b[i];
      y = std::min(y, a*x+b);
      i >>= 1;
    }
    return y;
  }
};


#line 11 "test/yj_line_add_get_min_li_chao_tree.test.cpp"

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  std::vector<std::tuple<int, intmax_t, intmax_t>> qs;
  qs.reserve(n+q);
  std::map<intmax_t, size_t> enc;
  for (size_t i = 0; i < n; ++i) {
    intmax_t a, b;
    scanf("%jd %jd", &a, &b);
    qs.emplace_back(0, a, b);
  }
  for (size_t i = 0; i < q; ++i) {
    int t;
    scanf("%d", &t);
    if (t == 0) {
      intmax_t a, b;
      scanf("%jd %jd", &a, &b);
      qs.emplace_back(0, a, b);
    } else if (t == 1) {
      intmax_t p;
      scanf("%jd", &p);
      enc[p];
      qs.emplace_back(1, p, 0);
    }
  }

  size_t m = 0;
  std::vector<intmax_t> xs;
  xs.reserve(enc.size());
  for (auto& [d, e]: enc) xs.push_back(d), e = m++;

  lower_linear_envelope<intmax_t, li_chao_tree_tag> lle(xs.begin(), xs.end());
  for (auto [t, a, b]: qs) {
    if (t == 0) {
      lle.push(a, b);
    } else if (t == 1) {
      intmax_t y = lle.get_nth(enc.at(a));
      printf("%jd\n", y);
    }
  }
}