• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Li Chao Min a guest Dec 10th, 2018 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. //we assume here n = 1e6, use limits appropriate to the problem
2. struct Line //mx + b
3. {
4.     ll m;
5.     ll b;
6.     ld f(ld x)
7.     {
8.         return m*x + b;
9.     }
10. };
11.
12. ll f(Line L, ll x)
13. {
14.     return L.m*x + L.b;
15. }
16.
17. Line tr;
18. struct CHT_MIN //lichao tree
19. {
20.     void build(int lo = 1, int hi = 1e6+1, int cur = 1)
21.     {
22.         if (tr[cur].m == 0 && tr[cur].b == INF) return;
23.         tr[cur] = {0, INF};
24.         if (hi-lo == 1) return;
25.         int mid = (lo+hi)/2;
26.         build(lo, mid, cur*2);
27.         build(mid, hi, cur*2+1);
28.     }
29.     void upd(Line L, int lo = 1, int hi = 1e6+1, int cur = 1)
30.     {
31.         int mid = (lo+hi)/2;
32.         ll optMid = L.f(mid) < tr[cur].f(mid);
33.         ll optLow = L.f(lo ) < tr[cur].f(lo );
34.         if (optMid) swap(L, tr[cur]);
35.         if (hi-lo == 1) return;
36.         if (optMid != optLow) upd(L, lo, mid, cur*2);
37.         else upd(L, mid, hi, cur*2+1);
38.     }
39.     ll get(int x, int lo = 1, int hi = 1e6+1, int cur = 1)
40.     {
41.         int mid = (lo+hi)/2;
42.         ll val = f(tr[cur], x);
43.         if (hi-lo == 1) return val;
44.         if (x < mid) return min(val, get(x, lo, mid, cur*2));
45.         else return min(val, get(x, mid, hi, cur*2+1));
46.     }
47. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top