Submission #69329893

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (int i=0; i<n; i++) cin >> a[i];

	// ans(L, R) 	= sum[l=L..R](sum[r=l..R](p[r] - p[l-1]))
	// 				= sum[l=L..R](-p[l-1] * (R-l+1) + sum[r=l..R](p[r]))
	// 				= sum[l=L..R](l * p[l-1] - (R+1) * p[l-1] + p2[R] - p2[l-1])
	// 				= sum[l=L..R](l * p[l-1]) - sum[l=L..R]((R+1) * p[l-1]) + (R-L+1) * p2[R] - p3[R-1] + p3[L-2]
	// 				= p4[R] - p4[L-1] - (R+1) * (p2[R-1] - p2[L-2]) + (R-L+1) * p2[R] - p3[R-1] + p3[L-2]

	vector<vector<long long>> p(4, vector<long long>(n+1, 0));
	for (int i=1; i<=n; i++) p[0][i] = p[0][i-1] + a[i-1];
	for (int i=1; i<=n; i++) p[1][i] = p[1][i-1] + p[0][i];
	for (int i=1; i<=n; i++) p[2][i] = p[2][i-1] + p[1][i];
	for (int i=1; i<=n; i++) p[3][i] = p[3][i-1] + p[0][i-1] * i;

	while (q--) {
		int l, r;
		cin >> l >> r;

		long long ans = 
			p[3][r] - p[3][l-1]
			- (r+1) * (p[1][r-1] - (l-2 >= 0 ? p[1][l-2] : 0))
			+ (r-l+1) * p[1][r]
			- p[2][r-1] + (l-2 >= 0 ? p[2][l-2] : 0);

		cout << ans << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tcs = 1;
	// cin >> tcs;
	while (tcs--) {
		solve();
	}
	return 0;
}

Submission Info

Judge Result