首页 > 其他分享 >李超线段树

李超线段树

时间：2024-01-11 21:55:07浏览次数：35  
标签：int 线段 tr 李超 ln kmax dis

李超线段树

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

以模板题为例。

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转移。虽然时间开销不及斜率优化快，但在实现上无需考虑过多的细节，实现难度小。

标签：int,线段,tr,李超,ln,kmax,dis
From： https://www.cnblogs.com/ereoth/p/17959606

相关文章

  • 线段树笔记
    例\(1\)题目描述给定一个长为\(n\)的序列，有\(m\)次操作，每次操作为以下三种之一。修改序列中的一个数求序列中某连续一段所有数的两两乘积的和\(\text{mod}1000000007\)。求序列中某连续一段所有相邻两数乘积的和\(\text{mod}1000000007\)。做法一般单点修改的难点都在......
  • lazy线段树模板
    importjava.io.*;importjava.util.*;publicclassMain{staticintN=(int)1e5+10;staticlong[]arr=newlong[N];staticlong[]sum=newlong[N<<2];staticlong[]lazy=newlong[N<<2];staticintn,m;public......
  • 线段树板子
    packageICPC;importjava.util.*;importjava.math.*;importjava.io.*;importjava.text.DecimalFormat;importjava.text.NumberFormat;classnode{intl,r,max,cnt;}publicclassMain{staticBufferedReaderreader=newBufferedRead......
  • 线段树 2
    由于有两个操作，我们要对乘法和加法设置一个优先级我们来看看先乘后加，lazy2表示乘数，lazy1表示加数（前者初始值为\(1\)，后者初始值为\(0\)）根据我们对lazy的理解，一个节点的和的真实值，为这个节点到根节点的路径中，对每一个节点依次先乘lazy2再加lazy1得到的最终结果假设某一步时，和的中......
  • 线段上离p最近的点 - 投影方式
    点到线段的最近距离判断依据1)投影结果<0，则线段端点a离p最近2)投影结果>线段ab的长度，则线段端点b离p最近3)否则p在线段上的垂点为最近点 p与ab不共线时1)p在线段两侧2-a)p在线段内侧2-b)p在线段内侧2 p与ab共线时1) p在线段两侧 2-a)p在线段内侧2-b......
  • 吉司机线段树
    \(mxb\)为历史最大值，\(tg1,tg2,tg3,tg4\)分别对应最大值真实\(tag\)，其他值真实\(tag\)，最大值最大\(tag\)，其它值最大\(tag\)#include<bits/stdc++.h>usingnamespacestd;#defineN500005#defineintlonglongintn,m;inta[N];structTREE{ intsum[N*4],mxb[N......
  • 线段树与历史最值和区间最值问题
    线段树与历史最值问题P4314CPU监控Description给定数组\(\{a_i\}\)，维护以下操作。定义一个辅助数组\(\{b_i\}\)，每次操作完后令\(b_i=\max(a_i,b_i)\)。查询\(\max_{i=l}^{r}a_i\)（区间最值）查询\(\max_{i=l}^{r}b_i\)（历史最值）\(\foralli\in[l,r]\)，\(a_i\gets......
  • syoj.1827. 线段传送带题解
    前情提要-三分1827.线段传送带P2571[SCOI2010]传送带省流：三分套三分。在二维平面上有两个传送带，一个从A点到B点，一个从C点到D点，速度分别是p和q，在平面内其他点的速度为r。求A点到D点的最小速度。考虑从A到D的路程一定是\(AE+EF+FD\)，即通过这两个点连......
  • 线段树详解
    定义什么是线段树线段树是一种二叉搜索树，每个节点都存储了一个区间的问题。能够解决的问题序列维护修改以及查询区间上的最值、求和等，修改和查询的时间复杂度为\(O\)(\(log\)\(n\))。与其他RMQ算法的区别算法适用范围优点缺点线段树动态可执行的操作......
  • 简单线段树
    一、什么是线段树？线段树是怎样的树形结构?线段树是一种二叉搜索树，每个结点都存储了一个区间，也可以理解成一个线段，你要从这些线段上进行搜索操作得到你想要的答案。线段树能够解决什么样的问题？线段树的适用范围很广，可以在线维护修改以及查询区间上的最值，求和。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99