blob: e84ad86e0a6ffdcf665ad4a8f5a368356c20dc59 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
// Gerade hat kleinere Steigung als alle vorherigen.
struct Line {
ll m, c;
ll operator()(ll x) {return m*x+c;}
};
vector<Line> ls;
ll ptr = 0;
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) { // m fallend, Laufzeit O(1) amortisiert
while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
ls.pop_back();
}
ls.push_back({m, c});
ptr = min(ptr, sz(ls) - 1);
}
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);
}
|
