MC0457符咒封印

码蹄集OJ-符咒封印

题目
”我会给你q次询问，每次询问给你两个参数l和r，你需要计算出1×al+2×al+1…+(r-l+1)×ar的和。如果答案很大，你只需要算出其对998244353取模的结果。若你能算出正确结果，便可解封符咒，助你们通过火焰山。”

输入格式:第一行两个整数n,g(1＜n,q≤5x1e5)。
第二行n个整数a1~an(1＜ai＜1e9)。
接下来q行，每行两个整数l,r(1＜l＜r＜n)，表示q组询问。
输出格式：输出q行，表示对于每次询问的答案。

样例 1

输入：

3 1
3 2 1
2 3

复制

输出：

4

复制

本题相关知识点： 算法基础：前缀和 | 差分

代码：
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5*1e5+10;
const int mod = 998244353;
int n, q;
ll a[N]; 
int main(void)
{cin >> n >> q; for(int i = 1; i <= n; i++)cin >> a[i];// 预处理前缀和数组vector<ll> sum1(n+1, 0); vector<ll> sum2(n+1, 0); for(int i = 1; i <= n; i++) {sum1[i] = (sum1[i-1] + a[i]) % mod;sum2[i] = (sum2[i-1] + (i+1) * a[i] % mod) % mod;}while(q--) {int l, r;cin >> l >> r;ll s1 = (sum1[r] - sum1[l-1] + mod) % mod;ll s2 = (sum2[r] - sum2[l-1] + mod) % mod;ll ans = (s2 - l * s1 % mod + mod) % mod;cout << ans << endl;}return 0;
}