LiChaoTree

struct LiChaoTree {
  constexpr static long long inf = std::numeric_limits<long long>::max();

  struct Line {
    long long k;
    long long m;

    [[nodiscard]] long long get(long long x) const {
      return k * x + m;
    }

    Line(long long k, long long m) : k(k), m(m) {
      void(0);
    }
  };

  struct Node {
    int lft;
    int rgt;
    Line line;

    Node() : lft(0), rgt(0), line(0, -inf) {
      void(0);
    }
  };

  long long l;
  long long r;
  std::vector<Node> nodes;

  LiChaoTree(long long l, long long r) : l(l), r(r), nodes(1) {
    assert(l < r);
  }

  long long getImpl(int n, long long l, long long r, long long x) {
    long long res = nodes[n].line.get(x);
    long long m = l + (r - l) / 2;
    if (x < m) {
      if (nodes[n].lft != 0) {
        res = std::max(res, getImpl(nodes[n].lft, l, m, x));
      }
    } else {
      if (nodes[n].rgt != 0) {
        res = std::max(res, getImpl(nodes[n].rgt, m, r, x));
      }
    }
    return res;
  }

  long long get(long long x) {
    assert(l <= x && x < r);
    return getImpl(0, l, r, x);
  }

  void addImpl(int n, long long l, long long r, Line line) {
    if (nodes[n].line.get(l) < line.get(l)) {
      std::swap(nodes[n].line, line);
    }
    if (nodes[n].line.get(r - 1) >= line.get(r - 1)) {
      return;
    }
    long long m = l + (r - l) / 2;
    if (nodes[n].line.get(m - 1) >= line.get(m - 1)) {
      if (nodes[n].rgt == 0) {
        nodes[n].rgt = nodes.size();
        nodes.emplace_back();
      }
      addImpl(nodes[n].rgt, m, r, line);
    } else {
      std::swap(nodes[n].line, line);
      if (nodes[n].lft == 0) {
        nodes[n].lft = nodes.size();
        nodes.emplace_back();
      }
      addImpl(nodes[n].lft, l, m, line);
    }
  }

  void add(long long k, long long m) {
    addImpl(0, l, r, {k, m});
  }
};