BZOJ2388: 旅行规划(分块 凸包)

题意

题目链接

sol

直接挂队爷的题解了

分块题好难调啊qwq

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10;
const ll inf = 6e18;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, block, bel[maxn], bl[maxn], br[maxn], mx;
vector<int> con[maxn];
ll bg[maxn], d[maxn], a[maxn];
double slope(int x, int y) {
    return double (a[y] - a[x]) / (y - x);
}
void rebuild(int id) {
    vector<int> &v = con[id]; v.clear();
    for(int i = bl[id]; i <= br[id]; i++) {
        while(v.size() > 1 && (slope(v[v.size() - 2], i) >= (slope(v[v.size() - 2], v[v.size() - 1])))) v.pop_back();   
        v.push_back(i);
    }
}
ll find(vector<int> &v, double k, int lef) {
    int l = 0, r = v.size() - 1, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(mid == 0 || (slope(v[mid - 1], v[mid]) > k)) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return a[v[ans]] + 1ll * (v[ans] - lef + 1) * (-k);
}
void modify(int l, int r, int val) {
    for(int i = l; i <= min(r, br[bel[l]]); i++) a[i] += 1ll * val * (i - l + 1);
    rebuild(bel[l]);
    if(bel[l] != bel[r]) {
        for(int i = bl[bel[r]]; i <= r; i++) a[i] += 1ll * val * (i - l + 1);
    }
    for(int i = r + 1; i <= br[bel[r]]; i++) a[i] += 1ll * val * (r - l + 1);
    rebuild(bel[r]);
    for(int i = bel[l] + 1; i <= bel[r] - 1; i++) {
        bg[i] += 1ll * (bl[i] - l + 1) * val - val;
        d[i]  += val;
    }
    for(int i = bel[r] + 1; i <= mx; i++) bg[i] += 1ll * val * (r - l + 1);
}
ll query(int l, int r) {
    ll ans = -inf;
    for(int i = l; i <= min(r, br[bel[l]]); i++)
        chmax(ans, bg[bel[l]] + 1ll * (i - bl[bel[l]] + 1) * d[bel[l]] + a[i]);
    if(bel[l] != bel[r]) {
        for(int i = bl[bel[r]]; i <= r; i++) 
            chmax(ans, bg[bel[r]] + 1ll * (i - bl[bel[r]] + 1) * d[bel[r]] + a[i]);
    }
    for(int i = bel[l] + 1; i <= bel[r] - 1; i++) {
        chmax(ans, bg[i] + find(con[i], -d[i], bl[i]));
    }
    return ans;
}
signed main() {
    n = read();  block = sqrt(n);
    for(int i = 1; i <= n; i++) a[i] = read() + a[i - 1], bel[i] = (i - 1) / block + 1, chmax(mx, bel[i]);
//  for(int i = 1; i <= 16; i++) cout << a[i] << " ";
    for(int i = 1; i <= mx; i++)  bl[i] = (i - 1) * block + 1, br[i] = bl[i] + block - 1, rebuild(i);
    m = read();
    for(int i = 1; i <= m; i++) {
        int opt = read();
        if(opt == 0) {
            int l = read(), r = read(), v = read();
            modify(l, r, v);
        } else {
            int l = read(), r = read();
            cout << query(l, r) << '\n';
        }
    }
    return 0;
}
/*
16
51 -6867 25916 -19111 -23413 -282 7274 6888 15114 6563 18264 -11811 27336 14638 19495 -10931
1
1 9 16

*/