【学习笔记】线段树分裂、分治、二进制分组、李超线段树

学习笔记, 线段树

线段树分裂

我裂开

我合上

以某个键值为中点（一般是把前 $k$ 个元素分离出来，而不是把前 $k$ 个下标）将线段树分裂为两部分。就把两棵线段树重合的 $log$ 个节点新建出来，所以单次严格 $O(logn)$，实现非常直白！

应用条件比较苛刻，要有序，才能关于键值裂开。题不太有，比较经典的这道排序，容易发现每次排序的是连续区间，对于每个区间建权值线段树，新建区间时把波及到的原有区间分裂出重合部分的线段树即可。以后见到应用再回来写。

template 
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
98
99
100
101
102
// luogu_5494
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define mid ((l + r) >> 1)
using namespace std;

typedef long long ll;
const int N = 2e5 + 10, M = N * 60;
int n, m, a[N], idx, id;
int rt[N], ls[M], rs[M];
ll sz[M];

void upd(int x) {
    sz[x] = sz[ls[x]] + sz[rs[x]];
}

void build(int &x, int l, int r) {
    if (!x)
        x = ++idx;
    if (l == r) {
        scanf("%lld", &sz[x]);
        return;
    }
    build(ls[x], l, mid), build(rs[x], mid + 1, r);
    upd(x);
}

void insert(int &x, int l, int r, int p, int v) {
    if (!x)
        x = ++idx;
    if (l == r) {
        sz[x] += v;
        return;
    }
    p <= mid ? insert(ls[x], l, mid, p, v) : insert(rs[x], mid + 1, r, p, v);
    upd(x);
}

ll query(int x, int l, int r, int lx, int rx) {
    if (lx <= l && r <= rx) {
        return sz[x];
    }
    ll ret = 0;
    if (lx <= mid) ret = query(ls[x], l, mid, lx, rx);
    if (rx > mid) ret += query(rs[x], mid + 1, r, lx, rx);
    return ret;
}

void merge(int &x, int y, int l, int r) {
    if (!x || !y) { x |= y; return; }
    if (l == r) {
        sz[x] += sz[y]; return;
    }
    merge(ls[x], ls[y], l, mid);
    merge(rs[x], rs[y], mid + 1, r);
    upd(x);
}

void split(int &x, int &y, int l, int r, int lx, int rx) {
    if (!y)
        return;
    if (lx <= l && r <= rx) {
        x = y, y = 0; return;  // 把 y 合并到空子树 x 上去，放心直接 =
    }
    if (!x)
        x = ++idx;
    if (lx <= mid) split(ls[x], ls[y], l, mid, lx, rx);
    if (rx > mid) split(rs[x], rs[y], mid + 1, r, lx, rx);
    upd(y);  // !!!
    upd(x);
}

int ask(int x, int l, int r, int k) {
    if (k <= 0 || sz[x] < k) return -1;
    if (l == r) return l;
    if (k <= sz[ls[x]]) return ask(ls[x], l, mid, k);
    else return ask(rs[x], mid + 1, r, k - sz[ls[x]]);
}

int main() {
    cin >> n >> m;
    ++id;
    build(rt[id], 1, n);
    while (m--) {
        int op, x, y, z; scanf("%d%d", &op, &x);
        if (op == 1 || op == 4) scanf("%d", &y);
        else scanf("%d%d", &y, &z);
        if (!op) {
            ++id;
            split(rt[id], rt[x], 1, n, y, z);
        } else if (op == 1) {
            merge(rt[x], rt[y], 1, n);
        } else if (op == 2) {
            insert(rt[x], 1, n, z, y);
        } else if (op == 3) {
            printf("%lld\n", query(rt[x], 1, n, y, z));
        } else {
            printf("%d\n", ask(rt[x], 1, n, y));
        }
    }
    return 0;
}

线段树分治

把操作复制 $logn$ 份挂在线段树上 $logn$ 个节点下，最后统一做一遍。时间线段树就是这个。

二进制分组

玄学

李超线段树

维护的是坐标系，支持两个操作：

  1. 加入一条直线
  2. 查询所有加入直线与 $x = x_0$ 的最高交点。

线段树维护覆盖每个区间没被覆盖面积最多的那条线。如果当前区间中，加入的线段和目前面积最多的线段相交，只需看斜率和中点谁高就能判断谁在这个区间占的面积更大，输的那条往下递归。

这里运用了标记永久化的思想，查询就把沿途线段贡献取 max。

如果插入的是线段，需要先找到可插入的区间，再分别加，是两只 log 的。

template 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
namespace LCTree {
  #define mid (l + r >> 1)
  int ls[M], rs[M], idx;
  void ins(int &x, ll l, ll r, Func cur) {
    if (!x) { x = ++idx, f[x] = cur; return; }
    if (l == r) return f[x].F(l) < cur.F(l) ? f[x] = cur, (void)0 : (void)0;
    if (f[x].F(mid) < cur.F(mid)) f[x].k < cur.k ? ins(ls[x], l, mid, f[x]) : ins(rs[x], mid + 1, r, f[x]), f[x] = cur;
    else f[x].k > cur.k ? ins(ls[x], l, mid, cur) : ins(rs[x], mid + 1, r, cur);
  }
  ll qry(int x, ll l, ll r, ll p) {
    if (!x) return -1e16;
    if (l == r) return f[x].F(p);
    return max(f[x].F(p), p <= mid ? qry(ls[x], l, mid, p) : qry(rs[x], mid + 1, r, p));
  }
}; using namespace LCTree;