区間和(白駿11659号)を求めます

5055 ワード
古典主義の研究 テキストリンク


link : https://www.acmicpc.net/problem/11659
これは積算問題です.
要素の和に直接近づくには長い時間がかかります.
だから区間の和を求めて、並べます.
区間の値をxとyとし,y区間の和からx−1の和の配列を減算すると,区間の和を求めることができる.
#include <iostream>
using namespace std;

int arr[100001] = { 0, };

int main() {

	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		int num;
		cin >> num;
		if (i == 1) {
			arr[i] = num;
		}
		else {
			arr[i] = (num + arr[i - 1]);
		}
	}

	while (m--) {
		int x, y;
		cin >> x >> y;
		cout << arr[y] - arr[x - 1] << "\n";
	}

}
Espcmsコンテンツページ上下編バックグラウンド別手動ソート番号
JavaScript演算子