链接 & 题目大意

算法 & 数据结构

差分、单调队列

思路 & 推导过程

暴力 1

注意到我们可以直接模拟，但是这样的话复杂度很难优化，没有前景，需要考虑换一个暴力。

暴力 2

注意到我们需要统计每秒牛奶的浪费，所以可以想到一个奶牛在 $k$ 秒后传入的牛奶是前 $k$ 个奶牛容量的最小值，而只有当这个最小值大于当前奶牛容量才会导致牛奶浪费。

这样的暴力的有点在于不需要像第一个暴力每次基于一个动态的数组，这个暴力每次都是基于一个静态的数组（奶牛的容量），所以有发展前景。

具体实现可以看代码被注释的部分。

正解

我们可以枚举每个奶牛作为区间最小值的区间，这一点可以用单调队列统计。

然后发现，因为我们需要紧挨着区间的右边的那个奶牛的容量小于区间最小值，所以我们发现其实某个奶牛作为区间最小值的区间的右端点是固定的，而且这个奶牛对答案的贡献是随着 $k$ 增大依次递增的，而在这里我们可以用一个二次差分的技巧来实现。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
*/
int n, a[1000005], d[1000005], sum, m[1000005];
int lowbit(int x) {
    return x & (-x);
}
int t[1000005], t2[1000005];
void addmax(int x, int y) {
    a[x] = y;
    for (int i = x; i <= n * 2; i += lowbit(i)) {
        t[i] = a[i];
        for (int j = 1; j < lowbit(i); j *= 2) {
            t[i] = min(t[i], t[i - j]);
        }
    }
}
int qmin(int l, int r) {
    int maxn = 1e18;
    while (l <= r) {
        maxn = min(maxn, a[r]);
        r --;
        for (; r - lowbit(r) >= l; r -= lowbit(r)) {
            maxn = min(maxn, t[r]);
        }
    } 
    return maxn;
}
int r[1000005], l[1000005], d2[1000005];
int s[1000005];
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    memset(t, 0x7f, sizeof t);
    for (int i = 1; i <= n; i ++) cin >> a[i], sum += a[i], m[i] = a[i], addmax(i, a[i]);
    a[n + 1] = a[1];
    a[0] = a[n];
    // for (int i = 1; i <= n; i ++) d[i] = a[i];
    // d[0] = a[n];
    for (int i = n + 1; i <= 2 * n; i ++) a[i] = a[i - n], m[i] = m[i - n], addmax(i, a[i]);
    for (int i = 1; i <= n * 2; i ++) s[i] = s[i - 1] + a[i];
    stack <int> st;
    for (int i = n * 2; i >= 1; i --) {
        while (st.size() && a[st.top()] >= a[i]) st.pop();
        if (st.size()) r[i] = st.top();
        else r[i] = n * 2 + 1;
        st.push(i);
    }
    while (st.size()) st.pop();
    for (int i = 1; i <= n * 2; i ++) {
        while (st.size() && a[st.top()] > a[i]) st.pop();
        if (st.size()) l[i] = st.top();
        else l[i] = 0;
        st.push(i);
    }
    int pos = 0;
    a[pos] = 1e18;
    for (int i = 1; i <= n; i ++) if (a[i] < a[pos]) pos = i;
    for (int i = pos + 1; i <= pos + n; i ++) {
        if (r[i] != 2 * n + 1 && a[i] != a[pos]) {
            int ll = r[i] - i;
            int rr = r[i] - l[i];

            // cout << i << " " << ll << " " << rr << "\n";
            d2[ll] += a[i] - a[r[i]];
            d2[rr] -= a[i] - a[r[i]];
        } 
    }
    // cout << endl;
    // for (int i = pos + 1; i <= pos + n; i ++) {
        // if (a[i] <= a[pos]) continue;
        // cout << i << " " << 1 << " " << (r[i] - l[i] - 1 + 1) << "\n";
        // if (r[i] != n * 2 + 1) {
        //     d2[1] += a[i] - max(a[l[i]], a[r[i]]);
        //     d2[(r[i] - l[i] - 1) + 1] -= a[i] - max(a[l[i]], a[r[i]]);
        // }
    // }
    for (int i = 1; i <= n; i ++) {
        d[i] = 0;
        d[i] = d[i - 1] + d2[i];
    }
    for (int i = 1; i <= n; i ++) {
        m[i] = 0;
        m[i] = m[i - 1] + d[i];
    }
    for (int i = 1; i <= n; i ++) {
        cout << sum - m[i] << "\n";
    }
    // cout << qmin(1, 3) << "\n";
    // for (int j = 1; j <= n; j ++) {
    //     for (int i = n + 1; i <= n * 2; i ++) {
    //         // cout << i << " " << a[i] << " " << j << "\n";
    //         int minn = 1e18;
    //         // for (int k = i - j; k < i; k ++) {
    //         //     minn = min(minn, m[k]);
    //         // }
    //         minn = qmin(i - j, i - 1);
    //         // cout << minn << "\n";
    //         if (minn > m[i]) {
    //             sum -= (minn - m[i]);
    //             // a[i] = m[i];
    //         }
    //         else {
    //             // a[i] = d[i - 1];
    //         }
    //     }
    //     // for (int i = n + 1; i <= n * 2; i ++) d[i] = a[i];
    //     // for (int i = 1; i <= n; i ++) a[i] = a[i + n], d[i] = d[i + n];
    //     cout << sum << "\n";
    // }

    return 0;
}