题解：P15574 [USACO26FEB] Milk Buckets S

· · 题解

每个桶向下倒的牛奶数量是一定的，那么每个桶向下倒固定次数后下面的桶会翻，所以每个桶向下倒的时间都成周期。

若桶 i 周期为 k_i（相邻两次倒间隔为 k_i），那么桶 i+1 周期为 \lceil\frac{a_{i+1}}{a_i}\rceil\times k_i。

即 k_n=(a_1+1)\times\lceil\frac{a_2}{a_1}\rceil\times\lceil\frac{a_3}{a_2}\rceil\times...\times\lceil\frac{a_{n}}{a_{n-1}}\rceil。

若桶 i 第一次倒时间为 x，那么桶 i+1 第一次倒时间为 x+(\lceil\frac{a_{i+1}}{a_i}\rceil-1)*k_i+1=x+k_{i+1}-k_i+1。

即 n 第一次倒时间为 k_n+n-1（中间的 k 值全部抵消了）。

有了这两个值，最后的答案就可以简单计算了。

每次修改 a_i 只影响 i 式子中两个位置的值，简单处理即可。

但是直接写会有问题：周期太大存不下。解决方法也很简单，用线段树维护每个位置 \lceil\frac{a_{i+1}}{a_i}\rceil 的值即可。如果区间乘积太大直接设为无限就行。

AC code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5,inf=1e18+1;
int n,a[N],f[N],q,tr[N];
int mg(int x,int y){
    if(x==inf||y==inf)return inf;
    __int128 re=(__int128)x*y;
    if(re>inf)return inf;
    return (int)re;
}
void bd(int p,int l,int r){
    if(l==r){tr[p]=f[l];return;}
    int mi=l+r>>1;
    bd(p<<1,l,mi),bd(p<<1|1,mi+1,r);
    tr[p]=mg(tr[p<<1],tr[p<<1|1]);
}
void md(int p,int l,int r,int x,int v){
    if(l==r){tr[p]=v;return;}
    int mi=l+r>>1;
    if(x<=mi)md(p<<1,l,mi,x,v);
    else md(p<<1|1,mi+1,r,x,v);
    tr[p]=mg(tr[p<<1],tr[p<<1|1]);
}
void pr(__int128 x){
    if(x>9)pr(x/10);
    cout<<char(x%10+'0');
}
signed main(){
    ios::sync_with_stdio(0),cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    f[1]=a[1]+1;
    for(int i=2;i<=n;i++)
        f[i]=(a[i]+a[i-1]-1)/a[i-1];
    bd(1,1,n),cin>>q;
    while(q--){
        int x,v,t;cin>>x>>v>>t,a[x]=v;
        if(x==1){
            f[1]=a[1]+1,md(1,1,n,1,f[1]);
            if(n>=2){
                f[2]=(a[2]+a[1]-1)/a[1];
                md(1,1,n,2,f[2]);
            }
        }else if(x==n){
            f[n]=(a[n]+a[n-1]-1)/a[n-1];
            md(1,1,n,n,f[n]);
        }else{
            f[x]=(a[x]+a[x-1]-1)/a[x-1];
            md(1,1,n,x,f[x]);
            f[x+1]=(a[x+1]+a[x]-1)/a[x];
            md(1,1,n,x+1,f[x+1]);
        }
        if(t<n-1){cout<<"0\n";continue;}
        __int128 k=(t-n+1)/tr[1];
        pr(k*a[n]),cout<<'\n';
    }
    return 0;
}