欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-15 16:38:47
题意 "题目链接" Sol 直接挂队爷的题解了 分块题好难调啊qwq cpp include define LL long long using namespace std; const int MAXN = 1e6 + 10; const LL INF = 6e18; template inlin ......

题意

题目链接

sol

直接挂队爷的题解了

分块题好难调啊qwq

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

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

#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

*/