https://codeforces.com/gym/102465/problem/G
没打cf又摸鱼到这么晚。。。心虚下床看看队友写的题。。。下午想了好久没想出怎么做
这题转换成求前缀和以后就很好做了，如果是拼接的话，那么直接把权值和长度加起来就行，如果是取一段，我们考虑递归的去求lo和hi的前缀和然后相减就行
然后递归的时候，我们就是求s[id]串的前x的前缀和
如果s[id]是拼接的，那么如果x<=len[a]就直接a串里面递归，否则就加上val[a]整个串的值，再去递归b串，加上b串部分的值。
如果s[id]也是截取的，那么就去递归s[id]截取的那个串s[s[id]]求右端点的前缀和，然后由于s[id]在截取s[s[id]]过程中的左区间的前缀和pre[s[id]]之前已经求过了，那么就是右端点前缀和减去左端点前缀和就行了
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=3000,mo=1e9+7; ll sum[N]; ll val[N],pre[N],suf[N],len[N]; ll A[N],B[N],C[N],D[N]; char s[N]; ll findpre(int id,ll x){ //qian x if(id==0){ if(x==0) return 0; return sum[x-1]; } if(x==len[id]) return val[id]; if(A[id]==2){ int a=B[id],b=C[id]; if(x<=len[a]) return findpre(a,x); else return (val[a]+findpre(b,x-len[a]))%mo; } else{ long long ans=findpre(D[id],B[id]+x); ans-=pre[id]; return ans%mo; } } int main(){ int i,n,a; scanf("%d",&n); scanf("%s",s); len[0]=strlen(s); for(i=0;s[i];i++){ if(i==0) sum[i]=s[i]; else sum[i]=sum[i-1]+s[i]; val[0]+=s[i]; } for(i=1;i<n;i++){ scanf("%s",&s); if(s[0]=='S'){ scanf("%lld%lld%lld",&D[i],&B[i],&C[i]); //C[i]--; A[i]=1; pre[i]=findpre(D[i],B[i]); suf[i]=findpre(D[i],C[i]); val[i]=(suf[i]-pre[i])%mo; len[i]=C[i]-B[i]; } else{ scanf("%lld%lld",&B[i],&C[i]); A[i]=2; val[i]=(val[B[i]]+val[C[i]])%mo; len[i]=len[B[i]]+len[C[i]]; } val[i]%=mo; if(val[i]<0) val[i]+=mo; } // cout<<pre[1]<<" "<<suf[1]<<endl; cout<<val[n-1]<<endl; }
