Codeforces

分析

我们可以把题目中的过程看成二维网格上的游走，即每步可以向下或向右下走，代价为该列的权值，求从第一行走到 $(x, y)$ 的最短路。

注意到这样的最短路一定是先往下走若干步，然后往右下走到终点。因此设 $s$ 为 $a$ 的前缀和，那么从 $(1, i)$ 走到 $(x, y)$ 的最短路为 $s_y - s_i + a_i(x - y + i)$。我们要对每个询问求出 $i \in [x - y, y]$ 的最小值。

这个式子有询问与决策的乘积项，因此可以考虑斜率优化。设 $y_i = a_i i - s_i, x_i = a_i, k = x - y, pre = s_y$，那么上面的最短路可以写成 $\min_{\max\{1, x - y\} \leq i \leq y} \left\{pre + y_i - kx_i\right\}$ 的形式。于是我们可以维护 $(x_i, y_i)$ 的下凸壳，询问时在上面二分。

这里的二分有一个问题，就是并不能取到 $\max\{1, x - y\}$ 往右的决策点，因此我们需要先二分出二分的下界。

因为 $a_i$ 没有单调性，所以这里需要平衡树维护下凸壳。但是可以发现，如果 $i \leq j $ 且 $a_j$ 为 $a_{i..j}$ 的最小值，则 $j$ 一定比 $i$ 更优。因此我们可以直接把横坐标 $\geq a_i$ 的元素弹掉，因为这些元素已经不可能成为最优决策点了。这样子就只需要写一个单调栈了。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 100000 + 10;

int n, Q, a[N], s[N];
ll ans[N];
vector<pair<int, int>> q[N];
int sta[N], top = 0;

ll X(int i) { return a[i]; }
ll Y(int i) { return 1ll * a[i] * i - s[i]; }
double slope(int i, int j) {
    if (X(i) == X(j)) return Y(i) < Y(j) ? 1e18 : -1e18;
    else return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j));
}
ll F(int i, int k) { return Y(i) - k * X(i); }

int find(int lim) {
    int L = 1, R = top;
    while (L < R) {
        int mid = (L + R) >> 1;
        if (sta[mid] >= lim) R = mid;
        else L = mid + 1;
    }
    return L;
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
    Q = read();
    for (int i = 1; i <= Q; ++i) {
        int x = read(), y = read();
        q[y].emplace_back(x, i);
    }
    for (int i = 1; i <= n; ++i) {
        while (top && a[sta[top]] >= a[i]) --top;
        while (top > 1 && slope(sta[top - 1], sta[top]) >= slope(sta[top], i)) --top;
        sta[++top] = i;
        for (auto t : q[i]) {
            int x = t.first, id = t.second, k = i - x;
            int L = find(max(1, k)), R = top - 1;
            while (L < R) {
                int mid = (L + R + 1) >> 1;
                if (slope(sta[mid], sta[mid + 1]) <= k) L = mid;
                else R = mid - 1;
            }
            if (L < top && F(sta[L], k) > F(sta[L + 1], k)) ++L;
            ans[id] = F(sta[L], k) + s[i];
        }
    }
    for (int i = 1; i <= Q; ++i) printf("%lld\n", ans[i]);
    return 0;
}