https://oj.gxyzh.com/d/hzoj/contest/696606a2c01e1c1c7ca584dd
美食家
题解（法一）
不妨将每桶包子最多能吃的次数处理出来，存在 \(a_i\)。
每次吃一趟包子，可以求出共吃了多少包子，之后全局减法。
有这样的神秘递推式：
\[d_i=d_{i-1}+[d_{i-1}<a_i]
\]
\(d_n\) 即是的包子数。
直接模拟是 \(O(nm)\) 的，需要优化。
注意到当第 \(i\) 个包子不能吃后，之后的轮次也不能吃。
考虑用 势能线段树 维护。
节点记录 \(min(a_i-d_{i-1})\)，检测到 \(minn+val\le 0\) 就暴力更新子树。
均摊复杂度为 \(O((n+m)logn)\)
代码
#include<iostream>
#define int long long
#define lch (x<<1)
#define rch (x<<1|1)
using namespace std;
constexpr int N=1e5+5;
int n,m,X,w[N],a[N],ans;
struct Segment_Tree{int sum[N<<2],tag[N<<2],minn[N<<2];void push_down(int x){if(!tag[x])return;tag[lch]+=tag[x],minn[lch]+=tag[x];tag[rch]+=tag[x],minn[rch]+=tag[x];tag[x]=0;}int query(int x,int l,int r,int L,int R){if(l>r)return 0;if(l==L&&r==R)return sum[x];int mid=(L+R)>>1; push_down(x);if(r<=mid)return query(lch,l,r,L,mid);else if(mid+1<=l)return query(rch,l,r,mid+1,R);else return query(lch,l,mid,L,mid)+query(rch,mid+1,r,mid+1,R);}void build(int x,int L,int R){if(L==R){minn[x]=a[L]-query(1,1,L-1,1,n);if(minn[x]<=0)minn[x]=1e17;sum[x]=(minn[x]!=1e17); return;}int mid=(L+R)>>1; build(lch,L,mid),build(rch,mid+1,R);sum[x]=sum[lch]+sum[rch];minn[x]=min(minn[lch],minn[rch]);}void update(int x,int val,int L,int R){if(minn[x]==1e17)return;if(minn[x]+val>0){ minn[x]+=val,tag[x]+=val; return; }if(L==R){minn[x]=1e17,sum[x]=0; add(1,L+1,n,1,1,n);return;}int mid=(L+R)>>1; push_down(x);update(lch,val,L,mid),update(rch,val,mid+1,R);sum[x]=sum[lch]+sum[rch],minn[x]=min(minn[lch],minn[rch]);}void add(int x,int l,int r,int val,int L,int R){if(l>r||minn[x]==1e17)return;if(l==L&&r==R){if(minn[x]+val<=0)update(x,val,L,R);else minn[x]+=val,tag[x]+=val;return;}int mid=(L+R)>>1; push_down(x);if(r<=mid)add(lch,l,r,val,L,mid);else if(mid+1<=l)add(rch,l,r,val,mid+1,R);else add(lch,l,mid,val,L,mid),add(rch,mid+1,r,val,mid+1,R);sum[x]=sum[lch]+sum[rch];minn[x]=min(minn[lch],minn[rch]);}
}tr;
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>X;for(int i=1;i<=n;i++)cin>>w[i];for(int i=1,x;i<=n;i++){cin>>x,a[i]=i;if(w[i]>X)a[i]=0;else a[i]=(X-w[i])/x+1;}tr.build(1,1,n);for(int i=1;i<=m;i++){int x=tr.sum[1]; ans+=x;tr.add(1,1,n,-x,1,n);}cout<<ans<<'\n';return 0;
}
题解（法二）
还没看懂题解。