775 字
4 分钟
李超线段树
李超线段树是用于维护平面内线段关系的树.
全局插入版本,插入操作的复杂度为
#include <bits/stdc++.h>#define pr pair<ll, ll>#define ll long longusing namespace std;long long n, m, ans, k;const ll mod = 1e9 + 7;#define inf 1e12#define N 1e6 + 1int 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;}局部插入版本,插入操作的复杂度为
#include <bits/stdc++.h>#define pr pair<ll, ll>#define ll long longusing namespace std;long long n, m, ans, k;const ll mod = 1e9 + 7;#define inf 1e12#define N 1e6 + 1class 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;}上述两个版本的查询复杂度均为
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时