[USACO24FEB] Milk Exchange G

来源

题目描述

Farmer John 的 N（11≤N≤5⋅10^5）头奶牛排成一圈。第 i 头奶牛有一个容量为整数 ai​（1≤ai​≤10^9）升的桶。所有桶初始时都是满的。

每一分钟，对于 1≤i<N，奶牛 ii 会将其桶中所有牛奶传递给奶牛 i+1，奶牛 N 将其牛奶传递给奶牛 1。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 x 升牛奶同时收到 x 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过ai​，则多余的牛奶会损失。

在 1,2,…,N 的每一分钟后，所有奶牛总共还余下多少牛奶？

输入格式

输入的第一行包含 N。

第二行包含a1​,a2​,…,aN​。

输出格式

输出 N行，其中第 i行包含 i分钟后所有奶牛总共余下的牛奶量。

思路

        奶牛是按排成一圈的，常规套路可以把数组复制几遍方便处理。容易想到把最小的放到最左边，可以在右移的过程中把右边的给覆盖掉，在研究的时候可以更直观得看出来。

        下面是一个样例的示例图：

        在这里可以直观地看出来，每一个数字形成的图形是有规律的，大致是三角形或者是平行四边形。这里我门考虑每一个数字在每一行产生的贡献，比如第六的数字2，在第一行到第四行产生的贡献是2，4，6，8，在第四行到第五行是不变的，在第五行到第八行的贡献是8，6，4，2。其它的形状也可以用类似概括，可以发现这是一个递增的等差数列（公差为ai），一个不变的等差数列（公差为0），一个递减的等差数列（公差为-ai），对于一段区间，累加上一段等差数列，知道了首项和公差，我们可以用两次差分，前缀和实现。

比如：要实现的等差数列是a1,a1+d,a1+2d,a1+3d

           第一次要达到的是a1,d,d,d,d(做一次前缀和即可实现上面)

           这里就能明显地看出来这些同样的d可以用基础的差分前缀和实现。

        至于三个数列的起始点和终止点，可以用两次单调栈维护每个数字左右第一次小于它的数字。然后直接手推三个关系式子即可。

 add(1,min(i-l[i],r[i]-i),a[i],a[i]);
 add(min(i-l[i],r[i]-i)+1,max(i-l[i],r[i]-i),(min(i-l[i],r[i]-i))*a[i],0);
 add(max(i-l[i],r[i]-i)+1,r[i]-l[i]-1,(min(i-l[i],r[i]-i))*a[i]-a[i],-a[i]);

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int long long
const int N = 5e5 + 10;

int p[N*2],s[N*2],a[N*3],l[N*3],r[N*3],q[N*3],cnt;
inline void add(int l1,int r1,int x,int y){ //维护二阶差分
    if(r1<l1){
        return;
    }
    p[l1]+=x;
    p[r1+1]-=y*(r1-l1)+x;
    s[l1+1]+=y;
    s[r1+1]-=y;
}
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n*2]=a[i];
        a[i+n]=a[i];
        r[i]=3*n+1;
    }
    for(int i=1;i<=n*3;i++){
        while(cnt&&a[q[cnt]]>=a[i]){
            cnt--;
        }
        l[i]=q[cnt];
        q[++cnt]=i;
    }
    cnt=0;
    for(int i=n*3;i>=1;i--){
        while(cnt&&a[q[cnt]]>a[i]){
            cnt--;
        }
        if(cnt){
            r[i]=q[cnt];
        }
        q[++cnt]=i;
    }
    for(int i=1;i<=n;i++){
        l[i]=max(l[i+n],i)-n;
        r[i]=min(r[i+n],i+2*n)-n;
        add(1,min(i-l[i],r[i]-i),a[i],a[i]);
        add(min(i-l[i],r[i]-i)+1,max(i-l[i],r[i]-i),(min(i-l[i],r[i]-i))*a[i],0);
        add(max(i-l[i],r[i]-i)+1,r[i]-l[i]-1,(min(i-l[i],r[i]-i))*a[i]-a[i],-a[i]);
    }
    for(int i=1;i<=n;i++){
        s[i]+=s[i-1];
        p[i]+=s[i];
    }
    for(int i=2;i<=n;i++){
        p[i]+=p[i-1];
        cout<<p[i]<<'\n';
    }
    cout<<p[n];
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
//    cin>>T;
    while (T--)solve();
    return 0;
}