一个不太一样的解法

题目大意 西格玛都看得懂吧 给看不懂的解释一下： 比如数组A为 1 2 3 4 5 然后l=2,r=5 我们要求的就是 2*1+3*2+4*3+5*4=40 如果l=3,r=5 我们要求的就是 3*1+4*2+5*3=26 懂了没？

思考过程 主播总觉得这题要用前缀和 设A一共有4个元素 那么我们来写一个普通前缀和： a1 a1+a2 a1+a2+a3 a1+a2+a3+a4 但这显然不是我们要求的 而主播灵光一现 我们给前缀和做前缀和怎么样？ 于是我们就得到了： a1 a1*2+a2 a1*3+a2*2+a3 a1*4+a2*3+a3*2+a4 好像有点用！ 但这个系数是倒着的，所以我们改成后缀和： 普通后缀和： a1+a2+a3+a4 a2+a3+a4 a3+a4 a4 后缀和的后缀和： a1+a2*2+a3*3+a4*4 a2*1+a3*2+a4*3 a3+a4*2 a4 这时我感觉离答案很近了， 但我们要求的东西怎么表示呢？ 如果r=4,那么答案就是后缀和的后缀和的第l项 那如果r<4怎么办呢？ 比如l=1,r=2 我们要求的东西：a1+a2*2 但是后缀和的后缀和里面只有： a1+a2*2+a3*3+a4*4 我们需要减去(a3*3+a4*4) 我们就可以把(a3*3+a4*4)变成： (a3+a4*2)+(a3+a4)*2 而其中的两个括号在后缀和里面都有！ 于是多尝试几下就可以总结出我们要求的东西： 设普通后缀和为s,后缀和的后缀和为ss 要求的东西就是： ss[l]-ss[r+1]-s[r+1]*(r-l+1) 最后处理一下模数和文件操作就可以啦！

代码： #include using namespace std; const long long mod=998244353; long long n,a[200005],s[200005],ss[200005],q,l,r; int main() { freopen("pre.in","r",stdin); freopen("pre.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=n;i>=1;i--) s[i]=(s[i+1]+a[i])%mod; for(int i=n;i>=1;i--) ss[i]=(ss[i+1]+s[i])%mod; cin>>q; while(q--) { cin>>l>>r; cout<<(ss[l]-ss[r+1]+mod-(r-l+1)*s[r+1]%mod+mod)%mod<<'\n'; } return 0; }

完结撒花！！！ 记得点赞（为了我的硬币）

题目要求 $\sum_{i=l}^{r} (i-l+1)\ a[i]$

展开式子可得 $\sum_{i=l}^{r} i\ a[i] - (l-1) a[i]$

再展开得 $\sum_{i=l}^{r} i\ a[i]$ $-$ $(l-1)\sum_{i=l}^{r}a[i]$

维护 $i\ a[i]$ 和 $a[i]$ 两个前缀和即可。

代码就不给了。