775 字
4 分钟
李超线段树

李超线段树是用于维护平面内线段关系的树.

全局插入版本,插入操作的复杂度为 O(nlog(n))O(nlog(n))

#include <bits/stdc++.h>
#define pr pair<ll, ll>
#define ll long long
using namespace std;
long long n, m, ans, k;
const ll mod = 1e9 + 7;
#define inf 1e12
#define N 1e6 + 1
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
vector<int> tr((k + 1) * 4 + 5, 0);
vector<pr> segments;
auto cal = [&](ll x, int id) {
return (segments[id].second - segments[id].first) * (x - 1) / (k) + segments[id].first;
};
#define lc x << 1
#define rc x << 1 | 1
auto insert = [&](auto &&self, int x, int l, int r, int id) -> void {
ll mid = (l + r) >> 1;
if (cal(mid, id) > cal(mid, tr[x]))
swap(tr[x], id);
if (cal(l, id) > cal(l, tr[x]))
self(self, lc, l, mid, id);
if (cal(r, id) > cal(r, tr[x]))
self(self, rc, mid + 1, r, id);
};
auto query = [&](auto &&self, int x, int l, int r, int aim) -> ll {
auto mid = (l + r) >> 1;
auto ans = cal(aim, tr[x]);
if (l == r)
return ans;
if (aim <= mid)
return max(ans, self(self, lc, l, mid, aim));
else
return max(ans, self(self, rc, mid + 1, r, aim));
};
for (int i = 1; i <= n; i++) {
ll x, y;
cin >> x >> y;
segments.push_back({x, y});
insert(insert, 1, 1, k + 1, segments.size() - 1);
}
for (int i = 0; i <= k; i++) {
cout << query(query, 1, 1, k + 1, i + 1) << ' ';
}
return 0;
}

局部插入版本,插入操作的复杂度为 O(nlog2(n))O(nlog^2(n))

#include <bits/stdc++.h>
#define pr pair<ll, ll>
#define ll long long
using namespace std;
long long n, m, ans, k;
const ll mod = 1e9 + 7;
#define inf 1e12
#define N 1e6 + 1
class Point {
public:
ll x = 0, y = 0;
ll operator*(const Point &oth) const { return x * oth.x + y * oth.y; }
ll operator^(const Point &oth) const { return x * oth.y - y * oth.x; }
Point operator+(const Point &oth) const { return {x + oth.x, y + oth.y}; }
Point operator-(const Point &oth) { return {x - oth.x, y - oth.y}; }
ll dis(const Point &oth) { return (x - oth.x) * (x - oth.x) + (y - oth.y) * (y - oth.y); }
bool operator<(const Point &oth) { return make_pair(x, y) < make_pair(oth.x, oth.y); }
};
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> k;
vector<int> tr((k + 1) * 4 + 5, 0);
vector<pair<Point, Point>> segments{{{0, -1}, {k + 1, -1}}};
auto cal = [&](ll x, int id) {
x--;
auto now = segments[id].second - segments[id].first;
auto kk = (now.y) / now.x;
return kk * x + segments[id].second.y - segments[id].second.x * kk;
};
#define lc x << 1
#define rc x << 1 | 1
auto insert = [&](auto &&self, int x, int l, int r, int L, int R, int id) -> void {
ll mid = (l + r) >> 1;
if (l >= L && r <= R) {
if (cal(mid, id) > cal(mid, tr[x]))
swap(tr[x], id);
if (cal(l, id) > cal(l, tr[x]))
self(self, lc, l, mid, L, R, id);
if (cal(r, id) > cal(r, tr[x]))
self(self, rc, mid + 1, r, L, R, id);
return;
}
if (L <= mid)
self(self, lc, l, mid, L, R, id);
if (R > mid)
self(self, rc, mid + 1, r, L, R, id);
};
auto query = [&](auto &&self, int x, int l, int r, int aim) -> ll {
auto mid = (l + r) >> 1;
auto ans = cal(aim, tr[x]);
if (l == r)
return ans;
if (aim <= mid)
return max(ans, self(self, lc, l, mid, aim));
else
return max(ans, self(self, rc, mid + 1, r, aim));
};
for (int i = 1; i <= n; i++) {
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
segments.push_back({{x1, y1}, {x2, y2}});
insert(insert, 1, 1, k + 1, x1 + 1, x2 + 1, i);
}
for (int i = 0; i <= k; i++) {
cout << query(query, 1, 1, k + 1, i + 1) << ' ';
}
return 0;
}

上述两个版本的查询复杂度均为O(log(n))O(log(n))

李超线段树
https://sanzenin.top/posts/obsidian/李超线段树/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取