526互联

李超线段树

发布时间 2024-01-11 21:55:46作者: ereoth

李超线段树

李超线段树是一种求函数定点最值的线段树，思路高妙，用处也很广。

以模板题为例。

P4097 [HEOI2013] Segment

有 \(n\) 个操作，操作分两种。

  • 在平面上加入一条线段，两端端点为 \((x_0,y_0)\) 和 \((x_1,y_1)\)，第 \(i\) 条被插入的线段的标号为 \(i\)。
  • 给定整数 \(k\)，询问与直线 \(x=k\) 相交的线段中，交点纵坐标最大的线段的编号。
    \(n\le 10^5\)，要求操作强制在线。

定义一条线段在一个横坐标区间 \([l,r]\) 的最高跨度为这条线段在该区间作为最高的一段线段的长度，显然，一条线段作为最高线段的区间是连续的。

定义一个区间覆盖的优势最大的线段为该区间内最高跨度最大的线段。

在李超线段树中，每个节点记录的是区间内优势最大的线段编号。但李超线段树并不严格，只需要满足包括单点的所有线段树区间优势最大线段中含有该单点的优势最大线段即可。所以如果整个区间的优势最大线段的最高跨度为整个区间的长度，就不需要再继续往下更新了。这样一条线段最多更新 \(\log n\) 个区间。在单点查询的时候，将包含单点的所有区间的节点的优势最大线段代入计算纵坐标取最大值即可。

考虑新添加一条线段时如何更新节点区间的优势最大线段，分类讨论一下。

  • 如果区间没有任何线段，直接设为优势最大线段；
  • 如果区间存在优势最大线段，
    • 新加的线段两端都高于当前最大优势线段，直接设为优势最大线段；
    • 新加的线段两端都低于当前最大优势线段，不予考虑；
    • 新线段斜率小于当前最大优势线段，且新线段与区间中点位置交点更高，则左半区间直接更新为新线段，递归更新右儿子区间；
    • 新线段斜率小于当前最大优势线段，且新线段与区间中点位置交点更低，则右半区间保持原先的线段不变，递归更新左儿子区间；
    • 新线段斜率大于当前最大优势线段，且新线段与区间中点位置交点更高，则右半区间直接更新为新线段，递归更新左儿子区间；
    • 新线段斜率大于当前最大优势线段，且新线段与区间中点位置交点更低，则左半区间保持原先的线段不变，递归更新右儿子区间；

画图的话更容易理解一些。

struct Line { // 线段
  double k, b;

  double f(int x) { // 计算纵坐标
    return k * (x - 1) + b;
  }
} ln[kmax];

struct Tree {
  int s; // 优势最大线段的编号
} tr[kmax << 2];

void Insert(int x, int l, int r, int k) {
  if(ln[k].f(l) <= ln[tr[x].s].f(l) && ln[k].f(r) <= ln[tr[x].s].f(r)) return; // 新线段两端点都更低
  if(ln[k].f(l) > ln[tr[x].s].f(l) && ln[k].f(r) > ln[tr[x].s].f(r)) return (void)(tr[x].s = k); // 新线段两端点都更高
  int mid = (l + r) >> 1;
  if(ln[k].k > ln[tr[x].s].k) { // 斜率
    if(ln[k].f(mid) > ln[tr[x].s].f(mid)) { // 比较与中点位置的交点
      Insert(x << 1, l, mid, tr[x].s);
      tr[x].s = k;
    } else {
      Insert(x << 1 | 1, mid + 1, r, k);
    }
  } else {
    if(ln[k].f(mid) > ln[tr[x].s].f(mid)) {
      Insert(x << 1 | 1, mid + 1, r, tr[x].s);
      tr[x].s = k;
    } else {
      Insert(x << 1, l, mid, k);
    }
  }
}

bool Comp(int x, int y, int k) { // 比较求更优
  double fx = ln[x].f(k);
  double fy = ln[y].f(k);
  return fx > fy;
}

int Query(int x, int l, int r, int k) {
  if(l == r) return tr[x].s;
  int mid = (l + r) >> 1;
  int res;
  if(k <= mid) {
    res = Query(x << 1, l, mid, k);
  } else {
    res = Query(x << 1 | 1, mid + 1, r, k);
  }
  return Comp(tr[x].s, res, k) ? tr[x].s : res; // 儿子结果在与当前区间的结果取更优
}

P4254 [JSOI2008] Blue Mary 开公司

也是一道板子题，注意求的是最后求的不是线段编号而是函数值，结果要除以 \(100\)。

code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int kmax = 1e5 + 3;

struct Line {
  double k, b;

  double f(int x) {
    return k * (x - 1) + b;
  }
} ln[kmax];

struct Tree {
  int s;
} tr[kmax << 2];

int n, lc;
string op;

void Insert(int x, int l, int r, int k) {
  if(l == r) {
    if(ln[k].f(l) > ln[tr[x].s].f(l)) tr[x].s = k;
    return;
  }
  int mid = (l + r) >> 1;
  if(ln[k].f(mid) > ln[tr[x].s].f(mid)) swap(tr[x].s, k);
  if(ln[k].f(l) > ln[tr[x].s].f(l)) {
    Insert(x << 1, l, mid, k);
  } else {
    Insert(x << 1 | 1, mid + 1, r, k);
  }
}

bool Comp(int x, int y, int k) {
  double fx = ln[x].f(k);
  double fy = ln[y].f(k);
  return fx > fy;
}

int Query(int x, int l, int r, int k) {
  if(l == r) return tr[x].s;
  int mid = (l + r) >> 1;
  int res;
  if(k <= mid) {
    res = Query(x << 1, l, mid, k);
  } else {
    res = Query(x << 1 | 1, mid + 1, r, k);
  }
  return Comp(tr[x].s, res, k) ? tr[x].s : res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for(int i = 1, x; i <= n; i++) {
    cin >> op;
    if(op[0] == 'P') {
      lc++;
      cin >> ln[lc].b >> ln[lc].k;
      Insert(1, 1, kmax - 1, lc);
    } else {
      cin >> x;
      int res = Query(1, 1, kmax - 1, x);
      cout << (int)(ln[res].f(x) / 100) << '\n';
    }
  }
  return 0;
}

P4655 [CEOI2017] Building Bridges

考虑dp。定义 \(f_i\) 表示考虑了前 \(i\) 个柱子并强制保留第 \(i\) 个柱子的最小花费，记 \(s_i=\sum\limits_{j=1}^iw_j\)，转移方程易得

\[\begin{aligned} f_i&=\min\{f_j+(h_i-h_j)^2-\sum\limits_{k=i}^jw_k\}\\ &=h_i^2+s_{i-1}+\min\{f_j-2h_ih_j+h_j^2-s_j\} \end{aligned} \]

将 \(j\) 的部分单独拎出来，令 \(k=-2h_j\)，\(b=f_j+h_j^2-s_j\)，可以写成一条直线 \((k,b)\)，插入到李超线段树中，维护纵坐标最小的优势线段，求解时查询当 \(x=h_i\) 时的最小值，时间复杂度可以做到 \(O(n\log n)\)。

P4069 [SDOI2016] 游戏

显然 \(a\times dis+b\) 可以写成一条直线，那么显然可以用李超线段树来做。

将答案的式子展开，令 \(l=lca(x, y)\)。

  • 从 \(x\) 到 \(l\)，有

    \[y=-a\times dis_i+(a\times dis_x+b)\quad i\in \{x,\cdots,l\} \]

  • 从 \(y\) 到 \(l\)，有

    \[y=a\times dis_i+(a\times dis_x-2a\times dis_l)\quad i\in \{y,\cdots,l\} \]

显然是在树链剖分上维护套李超线段树，因为修改和查询的对象都是区间，所以要上传最小值更新答案。

code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int kmax = 2e5 + 3;

struct Line {
  int k;
  long long b;

  long long Calc(long long x) {
    return x * k + b;
  }
};

struct E {
  int y, w;
};

struct Tree {
  long long v;
  Line ln;

  Tree() {
    ln.k = 0;
    v = ln.b = 123456789123456789ll;
  }
} tr[kmax << 2];

int n, m;
vector<E> e[kmax];
int d[kmax], siz[kmax], son[kmax];
int f[kmax], dfn[kmax], num[kmax], idx, top[kmax];
long long dis[kmax];

void Dfs(int x, int fa) {
  d[x] = d[fa] + 1, f[x] = fa;
  siz[x] = 1;
  for(auto cur : e[x]) {
    int y = cur.y;
    if(y == fa) continue;
    dis[y] = dis[x] + cur.w;
    Dfs(y, x);
    siz[x] += siz[y];
    if(siz[y] > siz[son[x]]) son[x] = y;
  }
}

void Dfss(int x, int tp) {
  dfn[x] = ++idx, num[idx] = x;
  top[x] = tp;
  if(son[x]) Dfss(son[x], tp);
  for(auto cur : e[x]) {
    int y = cur.y;
    if(y == f[x] || y == son[x]) continue;
    Dfss(y, y);
  }
}

int Lca(int x, int y) {
  while(top[x] != top[y]) {
    if(d[top[x]] < d[top[y]]) swap(x, y);
    x = f[top[x]];
  }
  if(d[x] > d[y]) swap(x, y);
  return x;
}


void Pushup(int x, int l, int r) {
  tr[x].v = min(tr[x].v, min(tr[x << 1].v, tr[x << 1 | 1].v));
  tr[x].v = min(tr[x].v, min(tr[x].ln.Calc(dis[num[l]]), tr[x].ln.Calc(dis[num[r]])));
}

void Modify(int x, int l, int r, int _l, int _r, Line ln) {
  if(_l <= l && r <= _r) {
    int mid = (l + r) >> 1;
    if(ln.Calc(dis[num[mid]]) < tr[x].ln.Calc(dis[num[mid]])) swap(ln, tr[x].ln);
    if(ln.Calc(dis[num[l]]) < tr[x].ln.Calc(dis[num[l]])) Modify(x << 1, l, mid, _l, _r, ln);
    if(ln.Calc(dis[num[r]]) < tr[x].ln.Calc(dis[num[r]])) Modify(x << 1 | 1, mid + 1, r, _l, _r, ln);
    Pushup(x, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  if(_l <= mid) Modify(x << 1, l, mid, _l, _r, ln);
  if(_r > mid) Modify(x << 1 | 1, mid + 1, r, _l, _r, ln);
  Pushup(x, l, r);
}

long long Query(int x, int l, int r, int _l, int _r) {
  if(_l <= l && r <= _r) return tr[x].v;
  int mid = (l + r) >> 1;
  long long res = min(tr[x].ln.Calc(dis[num[max(l, _l)]]), tr[x].ln.Calc(dis[num[min(r, _r)]]));
  if(_l <= mid) res = min(res, Query(x << 1, l, mid, _l, _r));
  if(_r > mid) res = min(res, Query(x << 1 | 1, mid + 1, r, _l, _r));
  return res;
}

void Update(int x, int y, Line v) {
  while(top[x] != top[y]) {
    if(d[top[x]] < d[top[y]]) swap(x, y);
    Modify(1, 1, n, dfn[top[x]], dfn[x], v);
    x = f[top[x]];
  }
  if(dfn[x] > dfn[y]) swap(x, y);
  Modify(1, 1, n, dfn[x], dfn[y], v);
}

long long Getres(int x, int y) {
  long long res = 123456789123456789ll;
  while(top[x] != top[y]) {
    if(d[top[x]] < d[top[y]]) swap(x, y);
    res = min(res, Query(1, 1, n, dfn[top[x]], dfn[x]));
    x = f[top[x]];
  }
  if(dfn[x] > dfn[y]) swap(x, y);
  res = min(res, Query(1, 1, n, dfn[x], dfn[y]));
  return res;
}

int main () {
  cin >> n >> m;
  for(int i = 1, x, y, w; i < n; i++) {
    cin >> x >> y >> w;
    e[x].push_back({y, w});
    e[y].push_back({x, w});
  }
  Dfs(1, 0);
  Dfss(1, 1);
  for(int i = 1, op, x, y, l, a, b; i <= m; i++) {
    cin >> op;
    if(op == 1) {
      cin >> x >> y >> a >> b;
      l = Lca(x, y);
      Update(x, l, {-a, dis[x] * a + b});
      Update(l, y, {a, dis[x] * a - dis[l] * a * 2 + b});
    } else {
      cin >> x >> y;
      printf("%lld\n", Getres(x, y));
    }
  }
	return 0;
}

总结一下，李超线段树可以很优雅地解决在线插入线段，求区间线段交点最值。在实际的应用中，李超线段树可以类似斜率优化一样优化dp转移。虽然时间开销不及斜率优化快，但在实现上无需考虑过多的细节，实现难度小。