题解：P15574 [USACO26FEB] Milk Buckets S
NegetiveEdgeWeight
·
·
题解
题解：P15574 [USACO26FEB] Milk Buckets S
某边权太笨了忘记了打二月的 USACO，只能给 S 组写题解了。
简要题意
给定一个序列 b_1,b_2,\dots,b_n，初始值均为 0。每一时刻将 b_1 的值加一。
当 b_i 在时刻 t 的值达到 a_i，则在 t+1 秒开始时翻转，将 b_{i+1} 的值增加 b_i（若 i=N 则将池子的价值增加 b_i），并在 t+1 秒结束时将 b_i 的值设为 0。
修改某个 a_i 后，求 t 秒后池子中的总价值。
思路
首先可以算出每层需要多少次上层翻转才会翻转。
对于每个 i\geq2，第 {i-1} 桶每次都会恰好倒出 a_{i-1}，所以第 i 桶需要上层倒 \lceil\frac{a_{i-1}}{a_{i}}\rceil 次，令这个值为 k_i。
令 p_i 表示第 i 桶翻转需要第 1 个桶注水多少秒，p_1=a_1+1。
有递推关系式 p_i=p_{i-1}\times k_i~(i\geq2)。
则 p_n=p_1 \times \prod_{i=1}^{n}
{k_i}。
由于上下层之间每次翻转需要至少间隔 1 秒，所以处理时将 t 的值减去 n-1。令 T=t-n+1。
现在有两种情况：
-
- 否则答案为 \lfloor \frac{T}{p_n} \rfloor\times a_n。
实现时可以用线段树维护 p_i 的值。
## 代码
```cpp
#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;a++)
#define Fro(a,b,c) for(int a=b;a>=c;a--)
#define lll __int128
#define int long long
using namespace std;
constexpr int N=2e5+5,MOD=998244353,LIM=2e18;
int n,q;
int a[N],seg[4*N];
int calcK(int i){
if(a[i]<=a[i-1])
return 1;
return (a[i]+a[i-1]-1)/a[i-1];
} //计算 p[n]
int mul(int x,int y){
if(x==0||y==0) return 0;
if(x>LIM||y>LIM) return LIM+1;
if(x>LIM/y) return LIM+1;
return x*y;
}
void build(int nd,int l,int r){
if(l==r){
seg[nd]=calcK(l);
return;
}
int mid=(l+r)/2;
build(nd*2,l,mid);
build(nd*2+1,mid+1,r);
seg[nd]=mul(seg[nd*2],seg[nd*2+1]);
}
void upd(int nd,int l,int r,int pos){
if(l==r){
seg[nd]=calcK(pos);
return;
}
int mid=(l+r)/2;
if(pos<=mid)
upd(nd*2,l,mid,pos);
else
upd(nd*2+1,mid+1,r,pos);
seg[nd]=mul(seg[nd*2],seg[nd*2+1]);
}
signed main(){
cin>>n;
For(i,1,n)
cin>>a[i];
build(1,2,n); //只维护 p[2] 到 p[n] 的值
cin>>q;
while(q--){
int idx,v,t;
cin>>idx>>v>>t;
a[idx]=v;
if(idx>=2) //处理越界
upd(1,2,n,idx);
if(idx+1<=n) //处理越界
upd(1,2,n,idx+1);
int PN=mul(a[1]+1,seg[1]),T=t-n+1;
if(T<=0||PN>T)
cout<<0<<'\n';
else
cout<<(int)((lll)(T/PN)*a[n])<<'\n';
}
return 0;
}
```