讀入

namespace {const int Maxlen = 1e7 + 5;char buf[Maxlen], *C = buf;int Len;inline void read_in() {Len = fread(C, 1, Maxlen, stdin);buf[Len] = '\0';}inline void fread(int &x) {x = 0;int f = 1;while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; }while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C;x *= f;}inline void fread(long long &x) {x = 0;long long f = 1;while (*C < '0' || '9' < *C) { if(*C == '-') f = -1; ++C; }while ('0' <= *C && *C <= '9') x = (x << 1) + (x << 3) + *C - '0', ++C;x *= f;}inline void read(int &x) {x = 0;int f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + c - '0'; c = getchar(); }x *= f;}inline void read(long long &x) {x = 0;long long f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }while(c >= '0' && c <= '9') { x = (x << 1ll) + (x << 3ll) + c - '0'; c = getchar(); }x *= f;} } View Code

斜率優化

namespace { struct Line { mutable ll k, m, p; bool f; // 存在斜率嗎 Line() {} Line(ll _k, ll _m, ll _p, bool _f) : k(_k), m(_m), p(_p), f(_f) {} bool friend operator < (const Line &a, const Line &b) { return (a.f && b.f) ? a.k < b.k : a.p < b.p; } }; struct LineContainer : multiset<Line> { // LineContainer() {} const ll inf = LLONG_MAX; ll div(ll a, ll b) { //求交點 return a / b - (a ^ b < 0 && a % b); } ld div(ld a, ld b) { return a / b; } bool Intersect(iterator x, iterator y) { if(y == end()) { x -> p = inf; return false; } if(x -> k == y -> k) x -> p = x -> m > y -> m ? inf : -inf; else x -> p = div(y -> m - x -> m, x -> k - y -> k); return x -> p >= y -> p; } void add(ll k, ll m) { multiset<Line> :: iterator z = insert(Line(k, m, 0, 1)), y = z++, x = y; while(Intersect(y, z)) z = erase(z); if(x != begin() && Intersect(--x, y)) Intersect(x, y = erase(y)); while((y = x) != begin() && (--x) -> p >= y -> p) Intersect(x, erase(y)); } ll query(ll x) { // assert(!empty()); multiset<Line> :: iterator L = lower_bound(Line(0, 0, x, 0)); return L -> k * x + L -> m; } }; } View Code

?

轉載于:https://www.cnblogs.com/2-321414133115/p/11205418.html

總結

以上是生活随笔為你收集整理的模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。