문제
수열 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 | #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;} |