李超线段树

P4097 【模板】李超线段树 / [HEOI2013] Segment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第 \(i\) 条被插入的线段的标号为 \(i\)。
2. 给定一个数 \(k\)，询问与直线 \(x = k\) 相交的线段中，交点纵坐标最大的线段的编号。

考虑线段树。我们对于线段树上的每个结点 \([tl, tr]\)，维护标记：

• 定义域完全包含 \([tl, tr]\) 的线段中，在 \(mid = \lfloor \frac {tl + tr}2 \rfloor\) 处纵坐标最大的一个。

因为我们做标记永久化，所以我们不需要保证这个标记每时每刻都是正确的，只需要保证根到这个结点的路径信息是对的即可。

那么查询时只需从根到叶子，每次和经过的结点维护的线段取答案即可。查询复杂度 \(\mathcal O(\log n)\)。

我们考虑修改，即插入一条线段。我们可以根据这条线段的两个端点求出这条线段所在直线的解析式 \(y = kx + b\)。

首先我们递归到每个被 \([l, r]\) 完全覆盖的极长的线段树中的结点（即普通的线段树修改区间时会访问的结点）。这样的结点有 \(\mathcal O(\log n)\) 个。令这个结点是 \([tl, tr]\)。我们考虑修改这个点（以及其它可能的点）的标记。

如果原来这个结点的标记不存在，或者这个标记完全在新的线段之下，那么直接将这个点的标记修改成新的线段即可。以下讨论的都是原来这个结点的标记存在的情况。

如果原标记完全在新的线段之上，那么没有影响，不需修改。

对于剩下的的情况，原标记一定与新线段交叉。那么我们可以先修改当前点的标记。

此时这个交叉点的位置会影响儿子的标记。具体的，当交叉点横坐标 \(\le mid\) 时，我们应该递归到左儿子继续处理。否则，当交叉点横坐标 \(>mid\) 时，应该递归到右儿子。不难发现这样的修改是 \(\mathcal O(\log n)\) 的。加上最开始的遍历到的线段树的节点数，修改复杂度为 \(\mathcal O(\log^2n)\)。

可读性极差的参考代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int q, cnt;

struct Line {
  long double k, b;
  long double y(int x) {
    return k * x + b;
  }
}a[N];

Line get(int x_0, int y_0, int x_1, int y_1) {    // 通过两个点求直线解析式
  Line res;
  res.k = (long double)(y_0 - y_1) / (x_0 - x_1);
  res.b = y_0 - res.k * x_0;
  return res;
}

int maxx(int x, int y, int k) {    // x，y 这两个函数，在 k 处谁的值更大？
  return a[x].y(k) > a[y].y(k) ? x : y;
}

struct Node {
  int l, r, tag;
}tr[N << 2];

void build(int u, int l, int r) {
  tr[u].l = l, tr[u].r = r;
  if (l != r) {
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
  }
}

void update(int u, int k) {    // 尝试通过直线 k 修改 u 的 tag
  cout << tr[u].l << ' ' << tr[u].r << ' ' << k << '\n';
  int mid = tr[u].l + tr[u].r >> 1;
  if (tr[u].l != tr[u].r) {
    if (tr[u].l == 6) cout << a[tr[u].tag].y(tr[u].l) << ' ' << a[k].y(tr[u].l) << '\n';
    if (a[tr[u].tag].y(tr[u].l) >= a[k].y(tr[u].l)) {
      update(u << 1, tr[u].tag);
    }
    if (a[tr[u].tag].y(tr[u].r) >= a[k].y(tr[u].r)) {
      update(u << 1 | 1, tr[u].tag);
    }
  }
  tr[u].tag = maxx(tr[u].tag, k, mid);
}

void modify(int u, int l, int r, int k) {    // 插入了定义域在 [l, r] 内的直线 k
  int mid = tr[u].l + tr[u].r >> 1;
  if (tr[u].l >= l && tr[u].r <= r) {
    int ori_l = a[tr[u].tag].y(tr[u].l);
    int ori_r = a[tr[u].tag].y(tr[u].r);
    int cur_l = a[k].y(tr[u].l);
    int cur_r = a[k].y(tr[u].r);
    
    if (ori_l >= cur_l && ori_r >= cur_r) return;
    if (ori_l < cur_l && ori_r < cur_r) tr[u].tag = k; 
    else {
      if (a[k].y(mid) > a[tr[u].tag].y(mid)) {
        swap(tr[u].tag, k);
        swap(ori_l, cur_l), swap(ori_r, cur_r);
      }
      
      if (cur_l > ori_l) modify(u << 1, l, r, k);
      else modify(u << 1 | 1, l, r, k);
    }
  }
  else {
    if (l <= mid) modify(u << 1, l, r, k);
    if (r > mid) modify(u << 1 | 1, l, r, k);
  }
}

int query(int u, int k) {
  if (tr[u].l == tr[u].r) return tr[u].tag;
  int mid = tr[u].l + tr[u].r >> 1;
  if (k <= mid) return maxx(tr[u].tag, query(u << 1, k), k);
  return maxx(tr[u].tag, query(u << 1 | 1, k), k);
}

int res[N];
int Y[N];

int main() {
  cin >> q;
  
  a[0].k = 0, a[0].b = -114514;
  
  build(1, 1, 40000);
  
  int lst = 0;
  while (q -- ) {
    int op;
    cin >> op;
    if (!op) {
      int k;
      cin >> k;
      k = (k + lst - 1) % 39989 + 1;
      
      int t = query(1, k);
      if (!t || (a[t].y(k) < Y[res[k]] || a[t].y(k) == Y[res[k]] && res[k] < t)) t = res[k];
      cout << (lst = t) << '\n';
    }
    else {
      int x_0, y_0, x_1, y_1;
      cin >> x_0 >> y_0 >> x_1 >> y_1;
      x_0 = (x_0 + lst - 1) % 39989 + 1;
      x_1 = (x_1 + lst - 1) % 39989 + 1;
      y_0 = (y_0 + lst - 1) % 1000000000 + 1;
      y_1 = (y_1 + lst - 1) % 1000000000 + 1;
      
      if (x_0 > x_1) {
        swap(x_0, x_1);
        swap(y_0, y_1);
      }
      a[ ++ cnt] = get(x_0, y_0, x_1, y_1);
      
      if (x_0 != x_1) {
        modify(1, x_0, x_1, cnt);
      }
      else {
        if (y_0 < y_1) swap(y_0, y_1);
        Y[cnt] = y_0;
        if (!res[x_0] || y_0 > Y[res[x_0]]) res[x_0] = cnt;
      }
    }
  }
  
  return 0;
}