구간의 대표값

문제

수열 A가 주어졌을 때, 주어지는 구간의 최소값, 최대값, 합을 구하여라.

---

입력

첫 번째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 100,000)

두 번째 줄에 수열의 각 수 Ai가 공백으로 분리되어 주어진다. (1 ≤ Ai ≤ 1,000,000,000)

세 번째 줄에 구간의 수 M이 주어진다. (1 ≤ M ≤ 100,000)

네 번째 줄부터 M개의 줄에 걸쳐 구간의 정보 a, b가 주어진다. 이는 수열의 구간 [a, b]에 대해 최소값, 최대값, 합을 구하라는 의미이다.

---

출력

각 질의에 대해 최소값, 최대값, 합을 공백으로 분리하여 출력한다. 이 때, 64-bit 정수형의 범위에서 답이 나올 수 있음에 유의하시오.

---

힌트

입력 예제

5

1 2 3 4 5

3

2 4

3 5

1 4

출력 예제

2 4 9

3 5 12

1 4 10

#include <iostream> #include <fstream> #include <limits.h> using std::cin; using std::cout; using std::endl; //어떤 구간의 최소값, 최대값, 합 구하기 //단위를 쪼갠다. //input 단위 100만 struct ANSWER { int min; int max; long long sum; }; int N; int M; int MINTREE[2000001]; //테스트는 1만 int MAXTREE[2000001]; //테스트는 1만 long long SUMTREE[2000001]; //테스트는 1만 int stdNum; void init() { for (int i = 1; i < stdNum; i++) { MINTREE[i] = INT_MAX; MAXTREE[i] = 0; SUMTREE[i] = 0; } for (int i = stdNum; i < stdNum + N; i++) { //부모노드를 따라서 계산; int pNum = i; while (pNum != 1) { pNum /= 2; if (MINTREE[i] < MINTREE[pNum]) MINTREE[pNum] = MINTREE[i]; if (MAXTREE[i] > MAXTREE[pNum]) MAXTREE[pNum] = MAXTREE[i]; SUMTREE[pNum] += (long long) SUMTREE[i]; } } } ANSWER getAnswer(int a, int b) { ANSWER answer = { INT_MAX, 0, 0 }; int l = stdNum + a -1; int r = stdNum + b -1; while (l <= r) { if ((l & 1) == 1) { //l이 오른쪽 자식이라면 answer.sum += SUMTREE[l]; if (answer.min > MINTREE[l]) { answer.min = MINTREE[l]; } if (answer.max < MAXTREE[l]) { answer.max = MAXTREE[l]; } l++; } if ((r & 1) != 1) { //r이 왼쪽 자식이라면 answer.sum += SUMTREE[r]; if (answer.min > MINTREE[r]) { answer.min = MINTREE[r]; } if (answer.max < MAXTREE[r]) { answer.max = MAXTREE[r]; } r--; } l /= 2; //부모로 올려줌 r /= 2; //부모로 올려줌 } return answer; } int main() { //std::ifstream cin("input.txt"); cin >> N; stdNum = 1; for (int i = N; i > 0; i /= 2) { stdNum *= 2; } int num; //값 입력받기 및 초기화 for (int i = stdNum; i < stdNum + N; i++) { cin >> num; //말단 노드 초기화 MINTREE[i] = num; MAXTREE[i] = num; SUMTREE[i] = num; } init(); cin >> M; int a, b; for (int i = 0; i < M; i++) { cin >> a >> b; ANSWER answer = getAnswer(a, b); cout << answer.min << " " << answer.max << " " << answer.sum <<endl; } return 0; }