题意：
思路：
因为只能一级级的升级，所以要升级到r级一定会先升级到l级。
dp[i]表示从1升到i级的花费，那么对于每次询问dp[r]-dp[l]就是答案（相当于维护一个前缀和）
状态转移：
因为每次从i级升到i+1级的成功率是不一定的，所以升级次数也是不一定的。假设第x次时升级到i+1级成功，所以前x-1次都是失败的。
dp[i+1]=dp[i]+a[i]+(t-1)*(a[i]+dp[i]-dp[x[i]]);
a[i]表示第x次升级的花费，后面的表示前x-1次的花费，dp[i]-dp[x[i]]表示从x[i]升级到i的花费。
因为第x次成功，也就是说x次成功了1次，即1/x=r/s;
注意取模和逆元。
代码：
const int maxn=1e6+100; int n,q; ll r[maxn],s[maxn],x[maxn],a[maxn]; ll dp[maxn]; ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } ll getinv(ll x) { return ksm(x,mod-2,mod); } int main() { int t;scanf("%d",&t); while(t--) { scanf("%d%d",&n,&q); for(int i=1; i<=n; i++) { scanf("%lld%lld%lld%lld",&r[i],&s[i],&x[i],&a[i]); ll invr=getinv(r[i]); ll t=s[i]*invr%mod; ll t1=(t-1+mod)%mod; dp[i+1]=t*((dp[i]+a[i])%mod)%mod; dp[i+1]=(dp[i+1]-t1*dp[x[i]]%mod+mod)%mod; } while(q--) { int l,r; scanf("%d%d",&l,&r); printf("%lld\n",(dp[r]-dp[l]+mod)%mod); } } return 0; }
![洛谷P3009-[USACO11JAN]Profits S（DP-最大子段和）](https://ucc.alicdn.com/images/user-upload-01/20200726131504871.png?x-oss-process=image/resize,h_160,m_lfit)