Submission #69344603

---

Source Code Expand

// 累積和を使って式変形をしたらすぐにできた…。
// [教訓] 図表を描いても見えないときは式変形しよう。
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n, q;
int a[300000];
int b[300001];
int rb1[300002];
int rb2[300002];

//[l, r)
int solve(int l, int r) {
	int res1 = rb2[r + 1] - rb2[l + 1];
	int res2 = l * (rb1[r + 1] - rb1[l + 1]);
	
	int res3 = rb2[r] - rb2[l];
	int res4 = r * (rb1[r] - rb1[l]);

	return res1 - res2 + res3 - res4;
}

signed main() {
	int i;
	
	cin >> n >> q;
	rep(i, n) cin >> a[i];
	rep(i, n) b[i + 1] = b[i] + a[i];

	rep(i, n + 1) rb1[i + 1] = rb1[i] + b[i];
	rep(i, n + 1) rb2[i + 1] = rb2[i] + i * b[i];

	rep(i, q) {
		int l, r;
		cin >> l >> r; l--;
		cout << solve(l, r) << endl;
	}
	return 0;
}

Submission Info

Judge Result