[BOJ/Gold 3] 백준 23327 리그전 오브 레전드(C++)

문제 링크

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

23327번: 리그전 오브 레전드

 

문제

최근 최고의 인기를 누리고 있는 인디 게임 "리그 파이트 매니저"는, 가상의 게임 "리그전 오브 레전드"의 E-sports 대회인 "리그전 오브 레전드 챔피언스 코리아"의 관리자가 되는 경영 게임이다.

이 대회는 그 이름답게, 각 팀이 리그전 내의 다른 모든 팀과 정확히 한번씩 경기를 치르는 방식으로 진행된다. 어떤 두 팀이 경기를 진행할 때, 그 경기의 재미는 두 팀의 인기의 곱과 동일하다. 또한 리그전의 재미는 그 리그전에서 치르는 모든 경기의 재미의 합이다. 예를 들어 어떤 리그전에 인기가 1,2,3인 세 팀이 참가했다면, 이 리그전의 재미는 (1×2)+(1×3)+(2×3)=11이 된다.

문제는 이번 대회에 너무 많은 팀이 참여를 원하여, 실력이 비슷한 팀들끼리 묶어 각각의 디비전으로 분리하여 대회를 진행하려고 한다. 즉, l번째로 잘하는 팀, l+1번째로 잘하는 팀, ..., r번째로 잘하는 팀을 묶어 하나의 디비전을 만들고, 이 디비전에 참여한 팀끼리 리그전을 진행한다. 한 디비전을 어떻게 구성할지 여러 개의 후보가 주어질 때, 각 후보 디비전의 재미를 구해보자.

입력

첫 번째 줄에 참가를 원하는 팀의 수 N(2≤N≤100000), 후보 디비전의 개수 Q(1≤Q≤200000)가 주어진다.

두 번째 줄에 정수 a1,a2,…,aN이 주어진다. ai는 i번째로 잘하는 팀의 인기를 의미한다. (1≤ai≤1000)

다음 Q개의 줄에 걸쳐, 각 후보 디비전을 나타내는 정수 l과 r(1≤l<r≤N)이 주어진다. 이것은 l≤i≤r를 만족하는 i에 대해서, i번째로 잘하는 팀들이 전부 리그전에 참가한다는 것을 의미한다.

출력

 Q개의 줄에 걸쳐 주어진 순서대로, 각 후보 디비전에서 진행되는 리그전의 재미를 출력한다.

예제 입력 1

5 3
5 1 2 3 2
2 4
4 5
1 5

예제 출력 1

11
6
63

•  l=2,r=4 : 인기가 [1,2,3]인 세 팀이 리그전에 참가한다. 이 리그전의 재미는 (1×2)+(1×3)+(2×3)=11이 된다.
•  l=4,r=5 : 인기가 [3,2]인 두 팀이 리그전에 참가한다. 이 리그전의 재미는 (3×2)=6이 된다.
•  l=1,r=5 : 인기가 [5,1,2,3,2]인 다섯 팀이 리그전에 참가한다.

알고리즘 분류

• 누적 합

풀이

배열 Sum에 1부터 N까지의 재미의 누적 합을 기록한다.

Q번의 디비전을 진행하는 동안, L이 1이라면 1번 팀부터 R번 팀까지의 재미의 합을 구하는 것이므로 R번째 재미의 누적 합을 출력하면 된다.

L이 1이 아니라면 L번 팀부터 R번 팀까지의 재미의 합을 구하는데, 이 때 R번째 재미의 누적 합에서 L-1번째 재미의 누적 합을 뺀다. 그리고 L~R번 팀이 1~L-1번 팀과 대결했을 때의 재미의 합을 빼주면 L번 팀부터 R번 팀까지의 재미의 합을 구할 수 있다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e9

using namespace std;
int N, Q;
LL A[MAX];
LL Sum[MAX];

void Input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		int X;
		cin >> X;
		A[i] = A[i - 1] + X;
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		Sum[i] = Sum[i - 1] + A[i - 1] * (A[i] - A[i - 1]);
	}
}

void Find_Answer() {
	while (Q--) {
		int L, R;
		cin >> L >> R;
		if (L == 1) {
			cout << Sum[R] << "\n";
		}
		else {
			cout << Sum[R] - (A[R] - A[L - 1]) * A[L - 1] - Sum[L - 1] << "\n";
		}
	};
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}