diff options
Diffstat (limited to 'datastructures/monotonicConvexHull.cpp')
| -rw-r--r-- | datastructures/monotonicConvexHull.cpp | 30 |
1 files changed, 16 insertions, 14 deletions
diff --git a/datastructures/monotonicConvexHull.cpp b/datastructures/monotonicConvexHull.cpp index 0049b3d..44bff83 100644 --- a/datastructures/monotonicConvexHull.cpp +++ b/datastructures/monotonicConvexHull.cpp @@ -1,25 +1,27 @@ // Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. -vector<ll> ms, bs; +struct Line { + ll m, b; + ll operator()(ll x) {return m*x+b;} +}; + +vector<Line> ls; int ptr = 0; -bool bad(int l1, int l2, int l3) { - return (bs[l3]-bs[l1])*(ms[l1]-ms[l2]) < - (bs[l2]-bs[l1])*(ms[l1]-ms[l3]); +bool bad(Line l1, Line l2, Line l3) { + return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m); } void add(ll m, ll b) { // Laufzeit O(1) amortisiert - ms.push_back(m); bs.push_back(b); - while (sz(ms) >= 3 && bad(sz(ms)-3, sz(ms)-2, sz(ms)-1)) { - ms.erase(ms.end() - 2); bs.erase(bs.end() - 2); + while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) { + ls.pop_back(); } - ptr = min(ptr, sz(ms) - 1); + ls.push_back({m, b}); + ptr = min(ptr, sz(ls) - 1); } -ll get(int idx, ll x) {return ms[idx] * x + bs[idx];} - ll query(ll x) { // Laufzeit: O(1) amortisiert - if (ptr >= sz(ms)) ptr = sz(ms) - 1; - while (ptr < sz(ms)-1 && get(ptr + 1, x) < get(ptr, x)) ptr++; - return get(ptr, x); -} + ptr = min(ptr, sz(ls) - 1); + while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++; + return ls[ptr](x); +}
\ No newline at end of file |