From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sat, 17 Aug 2024 20:30:08 +0200 Subject: improved monotonic onvex hull --- content/datastructures/monotonicConvexHull.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'content/datastructures/monotonicConvexHull.cpp') diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index e84ad86..f1721ae 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,5 +1,5 @@ // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue -// Gerade hat kleinere Steigung als alle vorherigen. +// Gerade hat kleineres pair(m, c) als alle vorherigen. struct Line { ll m, c; ll operator()(ll x) {return m*x+c;} @@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert +ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert ptr = min(ptr, sz(ls) - 1); while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++; return ls[ptr](x); -- cgit v1.2.3