Kris's Blog
0%

李超树

发表于 分类于

李超树是用于高效维护多个一次函数在某点极值的数据结构。

引

我们可以以类似权值线段树的形式，将一次函数的定义域作为线段树的区间。

当我们加入一条一次函数时，会与另外一条一次函数在一个区间内产生以下三种情况：

  • 完全在其上方
  • 完全在其下方
  • 存在一个交点

因为我们维护的仅有极值，只需要对旧极值一条一次函数进行判断。

对于前两种情况，直接覆盖区间即可。

而如果发现存在一个交点，则递归往交点所在的子区间下放标记。

举例来说，假设两条一次函数分别为 \(f(x)\) 和 \(g(x)\) 。

  • 在区间中点处 \(f(mid)\) 更优，则将 \(f\) 作为区间的标记。
  • 但发现在区间右端点处 \(g(r)\) 更优，说明在 \(mid - r\) 之间存在一个交点。因此向右区间递归下去。

查询则一路取标记中的极值即可。

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
struct L {
    double k;
    double b;

    double operator()(const int& x) { return k * x + b; }
} tree[MAX_N << 2];

void SegTree::mod(int x, int l, int r, L mv) {
    const auto mid = (l + r) >> 1;
    if (tree[x](mid) <= mv(mid)) {
        std::swap(tree[x], mv);
    }
    if (l == r) {
        return;
    }
    if (tree[x](l) <= mv(l)) {
        mod(lc, l, mid, mv);
    } else if (tree[x](r) <= mv(r)) {
        mod(rc, mid + 1, r, mv);
    }
}

double SegTree::query(int x, int l, int r, const int& qk) {
    if (l == r) {
        return tree[x](qk);
    }
    const auto mid = (l + r) >> 1;
    if (qk <= mid) {
        return std::max(tree[x](qk), query(lc, l, mid, qk));
    } else {
        return std::max(tree[x](qk), query(rc, mid + 1, r, qk));
    }
}

例

例1

板子题。也许主要的难度在于处理读入。1

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <cmath>
#include <cstdio>
#include <iostream>
#include <memory>

constexpr int MAX_N = 1000050;
constexpr int N = 1000000;

class SegTree {
   public:
    struct L {
        double k;
        double b;

        // 请注意本题中天数从 1 开始
        double operator()(const int& x) { return k * (x - 1) + b; }
    } tree[MAX_N << 2];

    SegTree() = default;
    ~SegTree() = default;

    void mod(int x, int l, int r, L mv);

    double query(int x, int l, int r, const int& qk);
};

template <typename T>
T read();

template <typename T>
void read(T& t);

template <typename T, typename... Args>
void read(T& t, Args&... rest);

template <>
char read();

template <>
double read();

int main() {
    std::ios::sync_with_stdio(false);

    auto segTree = std::make_unique<SegTree>();
    int T;
    read(T);
    while (T--) {
        char op;
        read(op);
        if (op == 'P') {
            double b, k;
            read(b, k);
            segTree->mod(1, 1, N, {k, b});
        } else if (op == 'Q') {
            int x;
            read(x);
            std::cout << (int)(segTree->query(1, 1, N, x)) / 100 << '\n';
        }
    }

    return 0;
}

#define lc (x << 1)
#define rc ((x << 1) | 1)

void SegTree::mod(int x, int l, int r, L mv) {
    const auto mid = (l + r) >> 1;
    if (tree[x](mid) <= mv(mid)) {
        std::swap(tree[x], mv);
    }
    if (l == r) {
        return;
    }
    if (tree[x](l) <= mv(l)) {
        mod(lc, l, mid, mv);
    } else if (tree[x](r) <= mv(r)) {
        mod(rc, mid + 1, r, mv);
    }
}

double SegTree::query(int x, int l, int r, const int& qk) {
    if (l == r) {
        return tree[x](qk);
    }
    const auto mid = (l + r) >> 1;
    if (qk <= mid) {
        return std::max(tree[x](qk), query(lc, l, mid, qk));
    } else {
        return std::max(tree[x](qk), query(rc, mid + 1, r, qk));
    }
}

#undef lc
#undef rc

template <typename T>
T read() {
    T x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar_unlocked();
    }
    return x * f;
}

template <typename T>
void read(T& t) {
    t = read<T>();
}

template <typename T, typename... Args>
void read(T& t, Args&... rest) {
    t = read<T>();
    read(rest...);
}

template <>
char read() {
    char ch = getchar_unlocked();
    while (ch != 'Q' and ch != 'P') {
        ch = getchar_unlocked();
    }
    return ch;
}

template <>
double read() {
    long long x = 0, f = 1, k = 0, b = 0;
    bool g = false;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch) or ch == '.') {
        if (ch == '.') {
            g = true;
        } else if (!g) {
            x = x * 10 + ch - 48;
        } else {
            b = b * 10 + ch - 48;
            k++;
        }
        ch = getchar_unlocked();
    }
    return f * (std::pow(0.1, k) * b + x);
}

例2

  • 给定 \(a_i, b_i\) ，其中 \(i \in [1,n]\) 。
  • 每次询问给出 \(p, k\)，求 \[ \max_{l \le p \le r}{\left( \sum_l^r{a_i} - k(\sum_l^r{b_i}) \right)} \]

首先对于包含 \(p\) 这个要求进行转化，可以转化为 \[\max_{1 \le l \le r \le p} + \max_{p+1 \le l \le r \le n}\]

我们以式子左半边为例，即 \[ \max_{1 \le l \le r \le p}{\left( \sum_{i=l}^r{a_i} - k(\sum_{i=l}^r{b_i}) \right)} \]

假设有 \[sa_x=\sum_{i=1}^{x}{a_i}, sb_x=\sum_{i=1}^{x}{b_i}\]

可以将原式转化成 \[\max_{1 \le l \le r \le p}{\left( \left( sa_r - sa_{l-1} \right) - k\left( sb_r - sb_{l-1} \right) \right)}\]

即是 \[ sa_r - k sb_r - \min_{0 \le l < r}{\left( k sb_l - sa_l \right)} \]

注意到 \(sb_l k - sa_l\) 是一次函数的形式，因此用李超树维护即可。

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <algorithm>
#include <climits>
#include <cstdio>
#include <iostream>
#include <memory>

using ll = long long;

constexpr int MAX_N = 1000050;
constexpr int N = 1000000;
constexpr ll INF = LLONG_MAX >> 4;

int a[MAX_N], b[MAX_N];
struct Q {
    int p;
    int k;
    int i;
} q[MAX_N];

class SegTree {
   public:
    struct L {
        ll k;
        ll b = INF;
        L() = default;
        L(ll k, ll b) { this->k = k, this->b = b; }
        // fxxk C++11, we need C++14!

        ll operator()(const ll& x) { return k * x + b; }
    } tree[MAX_N << 3];

    SegTree() = default;
    ~SegTree() = default;

    void mod(int x, int l, int r, L mv);

    ll query(int x, int l, int r, const ll& qk);
};

ll ans[MAX_N];

template <typename T>
T read();

template <typename T>
void read(T& t);

template <typename T, typename... Args>
void read(T& t, Args&... rest);

int main() {
    std::ios::sync_with_stdio(false);

    int n, m;
    read(n, m);
    for (int i = 1; i <= n; i++) {
        read(a[i], b[i]);
    }
    for (int i = 1; i <= m; i++) {
        read(q[i].p, q[i].k);
        q[i].i = i;
    }
    std::sort(q + 1, q + m + 1,
              [](const Q& x, const Q& y) { return x.p < y.p; });

    {
        std::unique_ptr<SegTree> segTree(new SegTree());
        ll sa{}, sb{};
        int i{1};
        for (int j = 1; j <= m; j++) {
            while (i <= n and i <= q[j].p) {
                segTree->mod(1, -N, N, {-sb, sa});
                sa += a[i];
                sb += b[i];
                i++;
            }
            ans[q[j].i] += sa - sb * q[j].k - segTree->query(1, -N, N, q[j].k);
        }
    }
    {
        std::unique_ptr<SegTree> segTree(new SegTree());
        ll sa{}, sb{};
        int i{n};
        for (int j = m; j >= 1; j--) {
            while (i >= 1 and i > q[j].p) {
                segTree->mod(1, -N, N, {-sb, sa});
                sa += a[i];
                sb += b[i];
                i--;
            }
            ans[q[j].i] += std::max(
                0ll, sa - sb * q[j].k - segTree->query(1, -N, N, q[j].k));
        }
    }

    for (int i = 1; i <= m; i++) {
        std::cout << ans[i] << '\n';
    }

    return 0;
}

#define lc (x << 1)
#define rc ((x << 1) | 1)

void SegTree::mod(int x, int l, int r, L mv) {
    const auto mid = (l + r) >> 1;
    if (tree[x](mid) >= mv(mid)) {
        std::swap(tree[x], mv);
    }
    if (l == r) {
        return;
    }
    if (tree[x](l) >= mv(l)) {
        mod(lc, l, mid, mv);
    } else if (tree[x](r) >= mv(r)) {
        mod(rc, mid + 1, r, mv);
    }
}

ll SegTree::query(int x, int l, int r, const ll& qk) {
    if (l == r) {
        return tree[x](qk);
    }
    const auto mid = (l + r) >> 1;
    if (qk <= mid) {
        return std::min(tree[x](qk), query(lc, l, mid, qk));
    } else {
        return std::min(tree[x](qk), query(rc, mid + 1, r, qk));
    }
}

#undef lc
#undef rc

template <typename T>
T read() {
    T x = 0, f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar_unlocked();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - 48;
        ch = getchar_unlocked();
    }
    return x * f;
}

template <typename T>
void read(T& t) {
    t = read<T>();
}

template <typename T, typename... Args>
void read(T& t, Args&... rest) {
    t = read<T>();
    read(rest...);
}

  1. [JSOI2008]Blue Mary开公司↩︎