diff options
Diffstat (limited to 'content/datastructures')
| -rw-r--r-- | content/datastructures/dynamicConvexHull.cpp | 2 | ||||
| -rw-r--r-- | content/datastructures/monotonicConvexHull.cpp | 6 |
2 files changed, 4 insertions, 4 deletions
diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp index d669847..dfcfe0b 100644 --- a/content/datastructures/dynamicConvexHull.cpp +++ b/content/datastructures/dynamicConvexHull.cpp @@ -4,7 +4,7 @@ struct Line { bool operator<(ll x) const {return p < x;} }; -struct HullDynamic : multiset<Line, less<>> { +struct HullDynamic : multiset<Line, less<>> { // max über Geraden // (for doubles, use inf = 1/.0, div(a,b) = a/b) ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);} diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp index 119015e..e84ad86 100644 --- a/content/datastructures/monotonicConvexHull.cpp +++ b/content/datastructures/monotonicConvexHull.cpp @@ -1,4 +1,4 @@ -// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue +// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue // Gerade hat kleinere Steigung als alle vorherigen. struct Line { ll m, c; @@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) { return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m); } -void add(ll m, ll c) { // Laufzeit O(1) amortisiert +void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) { ls.pop_back(); } @@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert ptr = min(ptr, sz(ls) - 1); } -ll query(ll x) { // Laufzeit: O(1) amortisiert +ll query(ll x) { // x steigend, 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); |