李超线段树

引入

洛谷 4097 [HEOI2013]Segment

要求在平面直角坐标系下维护两个操作（强制在线）：

在平面上加入一条线段。记第条被插入的线段的标号为，该线段的两个端点分别为，。
给定一个数，询问与直线相交的线段中，交点纵坐标最大的线段的编号（若有多条线段与查询直线的交点纵坐标都是最大的，则输出编号最小的线段）。特别地，若不存在线段与给定直线相交，输出。

数据满足：操作总数，，。

我们发现，传统的线段树无法很好地维护这样的信息。这种情况下，李超线段树 便应运而生。

过程

我们可以把任务转化为维护如下操作：

加入一个一次函数，定义域为；
给定，求定义域包含的所有一次函数中，在处取值最大的那个，如果有多个函数取值相同，选编号最小的。

注意

当线段垂直于轴时，会出现除以零的情况。假设线段两端点分别为和，，则插入定义域为的一次函数。

看到区间修改，我们按照线段树解决区间问题的常见方法，给每个节点一个懒标记。每个节点的懒标记都是一条线段，记为，表示要用更新该节点所表示的整个区间。

现在我们需要插入一条线段，考虑某个被新线段完整覆盖的线段树区间。若该区间无标记，直接打上用该线段更新的标记。

如果该区间已经有标记了，由于标记难以合并，只能把标记下传。但是子节点也有自己的标记，也可能产生冲突，所以我们要递归下传标记。

如图，按新线段取值是否大于原标记，我们可以把当前区间分为两个子区间。其中 肯定有一个子区间被左区间或右区间完全包含，也就是说，在两条线段中，肯定有一条线段，只可能成为左区间的答案，或者只可能成为右区间的答案。我们用这条线段递归更新对应子树，用另一条线段作为懒标记更新整个区间，这就保证了递归下传的复杂度。当一条线段只可能成为左或右区间的答案时，才会被下传，所以不用担心漏掉某些线段。

具体来说，设当前区间的中点为，我们拿新线段在中点处的值与原最优线段在中点处的值作比较。

如果新线段更优，则将和交换。那么现在考虑在中点处不如优的情况：

若在左端点处更优，那么和必然在左半区间中产生了交点，只有在左区间才可能优于，递归到左儿子中进行下传；
若在右端点处更优，那么和必然在右半区间中产生了交点，只有在右区间才可能优于，递归到右儿子中进行下传；
若在左右端点处都更优，那么不可能成为答案，不需要继续下传。

除了这两种情况之外，还有一种情况是和刚好交于中点，在程序实现时可以归入中点处不如优的情况，结果会往更优的一个端点进行递归下传。

最后将作为当前区间的懒标记。

下传标记：

实现

const double eps = 1e-9;

int cmp(double x, double y) {  // 因为用到了浮点数，所以会有精度误差
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

//...

void upd(int root, int cl, int cr, int u) {  // 对线段完全覆盖到的区间进行修改
  int &v = s[root], mid = (cl + cr) >> 1;
  if (cmp(calc(u, mid), calc(v, mid)) == 1) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v))  // 在此题中记得判线段编号
    upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
  // 上面两个 if 的条件最多只有一个成立，这保证了李超树的时间复杂度
}

拆分线段：

实现

void update(int root, int cl, int cr, int l, int r,
            int u) {  // 定位插入线段完全覆盖到的区间
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);  // 完全覆盖当前区间，更新当前区间的标记
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);  // 递归拆分区间
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

注意懒标记并不等价于在区间中点处取值最大的线段。

如图，加入黄色线段后，只有红色节点的标记被更新，而绿色节点的标记还未被改变。但在第二、三、四个绿色区间的中点处显然黄色线段取值最大。

查询时，我们可以利用标记永久化思想，在包含的所有线段树区间（不超过个）的标记线段中，比较得出最终答案。

查询：

实现

pdi query(int root, int l, int r, int d) {  // 查询
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

根据上面的描述，查询过程的时间复杂度显然为，而插入过程中，我们需要将原线段拆分到个区间中，对于每个区间，我们又需要花费的时间递归下传，从而插入过程的时间复杂度为。

[HEOI2013]Segment 参考代码

#include <iostream>
#include <string>
#define MOD1 39989
#define MOD2 1000000000
#define MAXT 40000
using namespace std;
typedef pair<double, int> pdi;

const double eps = 1e-9;

int cmp(double x, double y) {
  if (x - y > eps) return 1;
  if (y - x > eps) return -1;
  return 0;
}

struct line {
  double k, b;
} p[100005];

int s[160005];
int cnt;

double calc(int id, int d) { return p[id].b + p[id].k * d; }

void add(int x0, int y0, int x1, int y1) {
  cnt++;
  if (x0 == x1)  // 特判直线斜率不存在的情况
    p[cnt].k = 0, p[cnt].b = max(y0, y1);
  else
    p[cnt].k = 1.0 * (y1 - y0) / (x1 - x0), p[cnt].b = y0 - p[cnt].k * x0;
}

void upd(int root, int cl, int cr, int u) {  // 对线段完全覆盖到的区间进行修改
  int &v = s[root], mid = (cl + cr) >> 1;
  if (cmp(calc(u, mid), calc(v, mid)) == 1) swap(u, v);
  int bl = cmp(calc(u, cl), calc(v, cl)), br = cmp(calc(u, cr), calc(v, cr));
  if (bl == 1 || (!bl && u < v)) upd(root << 1, cl, mid, u);
  if (br == 1 || (!br && u < v)) upd(root << 1 | 1, mid + 1, cr, u);
}

void update(int root, int cl, int cr, int l, int r,
            int u) {  // 定位插入线段完全覆盖到的区间
  if (l <= cl && cr <= r) {
    upd(root, cl, cr, u);
    return;
  }
  int mid = (cl + cr) >> 1;
  if (l <= mid) update(root << 1, cl, mid, l, r, u);
  if (mid < r) update(root << 1 | 1, mid + 1, cr, l, r, u);
}

pdi pmax(pdi x, pdi y) {  // pair max函数
  if (cmp(x.first, y.first) == -1)
    return y;
  else if (cmp(x.first, y.first) == 1)
    return x;
  else
    return x.second < y.second ? x : y;
}

pdi query(int root, int l, int r, int d) {  // 查询
  if (r < d || d < l) return {0, 0};
  int mid = (l + r) >> 1;
  double res = calc(s[root], d);
  if (l == r) return {res, s[root]};
  return pmax({res, s[root]}, pmax(query(root << 1, l, mid, d),
                                   query(root << 1 | 1, mid + 1, r, d)));
}

int main() {
  ios::sync_with_stdio(false);
  int n, lastans = 0;
  cin >> n;
  while (n--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x0, y0, x1, y1;
      cin >> x0 >> y0 >> x1 >> y1;
      x0 = (x0 + lastans - 1 + MOD1) % MOD1 + 1,
      x1 = (x1 + lastans - 1 + MOD1) % MOD1 + 1;
      y0 = (y0 + lastans - 1 + MOD2) % MOD2 + 1,
      y1 = (y1 + lastans - 1 + MOD2) % MOD2 + 1;
      if (x0 > x1) swap(x0, x1), swap(y0, y1);
      add(x0, y0, x1, y1);
      update(1, 1, MOD1, x0, x1, cnt);
    } else {
      int x;
      cin >> x;
      x = (x + lastans - 1 + MOD1) % MOD1 + 1;
      cout << (lastans = query(1, 1, MOD1, x).second) << endl;
    }
  }
  return 0;
}

#ds

贡献者：@queenwen @Jimmy @WenzelTian @henrytb @Zirnc @do_while_true @Tang @Nathan @kenlig @mgt @Leo @Shuhao

本页面最近更新：2/3/2023, 12:00:00 AM，更新历史

发现错误？想一起完善？在 GitHub 上编辑此页！

本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

OI Wiki

李超线段树

引入

过程

0 条评论
未登录用户

李超线段树

引入

过程

0 条评论未登录用户

0 条评论
未登录用户