-
Notifications
You must be signed in to change notification settings - Fork 5
/
CHT (Convex Hull Trick).cpp
87 lines (81 loc) · 2.21 KB
/
CHT (Convex Hull Trick).cpp
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
struct line {
ll m, c; // y = mx+c
line(ll _m, ll _c) {
m = _m, c = _c;
}
};
struct CHT {
vector < line > vec;
ll t, ptr;
void init(ll x) {
t = x, ptr = 0;
vec.clear();
}
inline ll func(ll idx, ll x) {
return vec[idx].m * x + vec[idx].c;
}
bool bad(line f1, line f2, line f3) {
__int128 a = (f3.c - f1.c);
a = a * (f1.m - f2.m);
__int128 b = (f2.c - f1.c);
b = b * (f1.m - f3.m);
if(t == 1) return a <= b; // m_i > m_i+1. min query.
if(t == 2) return a >= b; // m_i > m_i+1. max query.
if(t == 3) return a >= b; // m_i < m_i+1. min query.
if(t == 4) return a <= b; // m_i < m_i+1. max query.
assert(0);
}
void add(line x) {
ll sz = vec.size();
while(sz >= 2 && bad(vec[sz - 2], vec[sz - 1], x)) {
vec.pop_back();
sz--;
}
vec.push_back(x);
}
ll ask(ll x) // ternary search
{
if(vec.empty())
return 0;
ll lo = 0, hi = vec.size() - 1;
ll ret = (t & 1)? mxlld : mnlld;
while(lo <= hi) {
ll mid1 = (lo + (hi - lo) / 3);
ll mid2 = (hi - (hi - lo) / 3);
ll ans1 = func(mid1,x);
ll ans2 = func(mid2,x);
if(ans1 > ans2) {
if(t & 1)
ret = min(ret, ans2), lo = mid1 + 1;
else
ret = max(ret, ans1), hi = mid2 - 1;
}
else {
if(t & 1)
ret = min(ret,ans1), hi = mid2 - 1;
else
ret = max(ret,ans2), lo = mid1 + 1;
}
}
return ret;
}
ll ask1(ll x) // pointer search (linear)
{
if(vec.empty())
return 0;
if(ptr >= vec.size()) ptr = vec.size() - 1;
while(ptr < (vec.size() - 1)) {
if(t & 1) {
if(func(ptr,x) > func(ptr + 1,x))
ptr++;
else break;
}
else {
if(func(ptr,x) < func(ptr + 1,x))
ptr++;
else break;
}
}
return func(ptr,x);
}
};