跳转至

李超線段樹

引入

洛谷 4097 [HEOI2013]Segment

要求在平面直角座標系下維護兩個操作（強制在線）：

  1. 在平面上加入一條線段。記第 \(i\) 條被插入的線段的標號為 \(i\)，該線段的兩個端點分別為 \((x_0,y_0)\)，\((x_1,y_1)\)。
  2. 給定一個數 \(k\)，詢問與直線 \(x = k\) 相交的線段中，交點縱座標最大的線段的編號（若有多條線段與查詢直線的交點縱座標都是最大的，則輸出編號最小的線段）。特別地，若不存在線段與給定直線相交，輸出 \(0\)。

數據滿足：操作總數 \(1 \leq n \leq 10^5\)，\(1 \leq k, x_0, x_1 \leq 39989\)，\(1 \leq y_0, y_1 \leq 10^9\)。

我們發現，傳統的線段樹無法很好地維護這樣的信息。這種情況下，李超線段樹 便應運而生。

過程

我們可以把任務轉化為維護如下操作：

  • 加入一個一次函數，定義域為 \([l,r]\)；
  • 給定 \(k\)，求定義域包含 \(k\) 的所有一次函數中，在 \(x=k\) 處取值最大的那個，如果有多個函數取值相同，選編號最小的。
注意

當線段垂直於 \(x\) 軸時，會出現除以零的情況。假設線段兩端點分別為 \((x,y_0)\) 和 \((x,y_1)\)，\(y_0<y_1\)，則插入定義域為 \([x,x]\) 的一次函數 \(f(x)=0\cdot x+y_1\)。

看到區間修改，我們按照線段樹解決區間問題的常見方法，給每個節點一個懶標記。每個節點 \(i\) 的懶標記都是一條線段，記為 \(l_i\)，表示要用 \(l_i\) 更新該節點所表示的整個區間。

現在我們需要插入一條線段 \(f\)，考慮某個被新線段 \(f\) 完整覆蓋的線段樹區間。若該區間無標記，直接打上用該線段更新的標記。

如果該區間已經有標記了，由於標記難以合併，只能把標記下傳。但是子節點也有自己的標記，也可能產生衝突，所以我們要遞歸下傳標記。

如圖，按新線段 \(f\) 取值是否大於原標記 \(g\)，我們可以把當前區間分為兩個子區間。其中 肯定有一個子區間被左區間或右區間完全包含，也就是説，在兩條線段中，肯定有一條線段，只可能成為左區間的答案，或者只可能成為右區間的答案。我們用這條線段遞歸更新對應子樹，用另一條線段作為懶標記更新整個區間，這就保證了遞歸下傳的複雜度。當一條線段只可能成為左或右區間的答案時，才會被下傳，所以不用擔心漏掉某些線段。

具體來説，設當前區間的中點為 \(m\)，我們拿新線段 \(f\) 在中點處的值與原最優線段 \(g\) 在中點處的值作比較。

如果新線段 \(f\) 更優，則將 \(f\) 和 \(g\) 交換。那麼現在考慮在中點處 \(f\) 不如 \(g\) 優的情況：

  1. 若在左端點處 \(f\) 更優，那麼 \(f\) 和 \(g\) 必然在左半區間中產生了交點，\(f\) 只有在左區間才可能優於 \(g\)，遞歸到左兒子中進行下傳；
  2. 若在右端點處 \(f\) 更優，那麼 \(f\) 和 \(g\) 必然在右半區間中產生了交點，\(f\) 只有在右區間才可能優於 \(g\)，遞歸到右兒子中進行下傳；
  3. 若在左右端點處 \(g\) 都更優，那麼 \(f\) 不可能成為答案，不需要繼續下傳。

除了這兩種情況之外，還有一種情況是 \(f\) 和 \(g\) 剛好交於中點，在程序實現時可以歸入中點處 \(f\) 不如 \(g\) 優的情況，結果會往 \(f\) 更優的一個端點進行遞歸下傳。

最後將 \(g\) 作為當前區間的懶標記。

下傳標記：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v))  // 在此題中記得判線段編號
    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 的條件最多隻有一個成立，這保證了李超樹的時間複雜度
}

拆分線段：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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);
}

注意懶標記並不等價於在區間中點處取值最大的線段。

如圖，加入黃色線段後，只有紅色節點的標記被更新，而綠色節點的標記還未被改變。但在第二、三、四個綠色區間的中點處顯然黃色線段取值最大。

查詢時，我們可以利用標記永久化思想，在包含 \(x\) 的所有線段樹區間（不超過 \(O(\log n)\) 個）的標記線段中，比較得出最終答案。

查詢：

實現 
1
2
3
4
5
6
7
8
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)));
}

根據上面的描述，查詢過程的時間複雜度顯然為 \(O(\log n)\)，而插入過程中，我們需要將原線段拆分到 \(O(\log n)\) 個區間中，對於每個區間，我們又需要花費 \(O(\log n)\) 的時間遞歸下傳，從而插入過程的時間複雜度為 \(O(\log^2 n)\)。

[HEOI2013]Segment 參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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;
  int bmid = cmp(calc(u, mid), calc(v, mid));
  if (bmid == 1 || (!bmid && u < v)) 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;
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用