李超线段树和set维护凸包

问题引入

有一些点 \((a_i, b_i)\)，需要多次询问 \(\max\{ax_0+b\}\)。

李超线段树

利用李超线段树可以很好地维护上述信息。

李超线段树就是支持 \(O(\log N)\) 插入直线和查询 \(\max{L_i(x)}\) 的数据结构。

线段树的每个节点保存 \(L(mid)\) 最大的那条直线。

插入一条直线时，比较 \(L_{old}(mid)\) 和 \(L_{new}(mid)\)，较大者保留，较小者继续递归。

constexpr int N(1e5 + 5);
struct Line {
  LL k, b;
  LL f(int x) {
    return k * x + b;
  }
} t[N << 2];
#define ls o << 1
#define rs o << 1 | 1
void ins(int o, int l, int r, Line x) {
  int m = l + r >> 1;
  bool lv = x.f(l) > t[o].f(l), mv = x.f(m) > t[o].f(m), rv = x.f(r) > t[o].f(r);
  if (mv) std::swap(x, t[o]);
  if (lv == rv || l == r) return;
  lv != mv ? ins(ls, l, m, x) : ins(rs, m + 1, r, x);
}
LL ask(int o, int l, int r, int x) {
  if (l == r) return t[o].f(x);
  int m = l + r >> 1;
  return std::max(t[o].f(x), x <= m ? ask(ls, l, m, x) : ask(rs, m + 1, r, x));
}

李超树可以合并，下面copy自jiangly的代码。

Node *merge(Node *p, Node *q, int l, int r) {
  if (p == nullptr)
    return q;
  if (q == nullptr)
    return p;
  int m = (l + r) / 2;
  p -> lc = merge(p -> lc, q -> lc, l, m);
  p -> rc = merge(p -> rc, q -> rc, m, r);
  modify(p, l, r, q -> line);
  return p;
}

也可以维护lazytag，和普通线段树一样，就是在修改的时候要把当前区间的直线往下放（这种没写过，下面的代码也是复制的，来自 Li Chao Tree Extended）。

void PushLine(Node* &n, data_t tl, data_t tr) {
  if (n == nullptr) return;
  data_t mid = (tl + tr) / 2;
  InsertLineKnowingly(n->lc, tl, mid, n->line);
  InsertLineKnowingly(n->rc, mid + 1, tr, n->line);
  n->line = Line<data_t>();
}

set 维护凸包

也可以用平衡树维护凸包来实现这个东西，有cf老哥搞了个set的版本，抄过来了。

constexpr LL QB = LLONG_MIN;
struct Line {
  LL a, b; // y = ax + b
  mutable std::function<const Line *()> next;
  bool operator<(const Line &r) const {
    if (r.b != QB) return a < r.a;
    auto q = next();
    if (!q) return 0;
    return b - q->b < (q->a - a) * r.a;
  }
};

using LLL = __int128;
struct DynamicHull : std::multiset<Line> {
  using multiset::multiset;

  bool bad(iterator y) {
    auto z = next(y);
    if (y == begin()) {
      if (z == end()) return false;
      return y->a == z->a && y->b <= z->b;
    }
    auto x = prev(y);
    if (z == end()) {
      return x->a == y->a && y->b <= x->b;
    }
    return LLL(x->b - y->b) * (z->a - y->a) >= LLL(y->b - z->b) * (y->a - x->a);
  }

  void ins(LL a, LL b) {
    auto it = insert({a, b});
    it->next = [=] {
      auto q = next(it);
      return q == end() ? nullptr : &*q;
    };

    if (bad(it)) {
      erase(it);
    } else {
      iterator z;
      while (it != begin() && bad(z = prev(it))) erase(z);
      it++;
      while (it != end() && bad(it)) it = erase(it);
    }
  }

  LL askMax(LL x) {
    auto l = *lower_bound({x, QB});
    return l.a * x + l.b;
  }
};

最后修改于 2022-03-08