취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 23327번 문제인 리그전 오브 레전드이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/23327 

a1, a2, ..., ak의 원소들이 있을 때 서로 (인덱스가) 다른 두 원소의 곱의 합은 (a1+a2+...+ak)^2 에서 (a1^2+a2^2+...+ak^2)을 빼는 것으로 계산해낼 수 있다. 단, 이 곱에는 a1*a2와 a2*a1과 같이 두 원소의 곱을 순서를 바꿔 더해 총 두번씩 들어있으므로 문제의 답은 위에서 계산한 값의 절반이 된다.

단순 누적합과 각 원소의 제곱의 누적합을 미리 전처리해 문제를 빠르게 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, Q;
ll psum1[100001]; // 누적합
ll psum2[100001]; // 제곱의 누적합

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		ll x; cin >> x;
		psum1[i] = psum1[i - 1] + x;
		psum2[i] = psum2[i - 1] + x * x;
	}

	while (Q--) {
		int L, R; cin >> L >> R; L--;
		cout << ((psum1[R] - psum1[L]) * (psum1[R] - psum1[L]) - (psum2[R] - psum2[L])) / 2 << '\n';
	}
}