문제
숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!
욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 _N_짜리 수열 _A_를 만들고, _A_를 비내림차순으로 정렬해서 수열 _B_를 만들어 버렸다!! 여기서 _B_를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 _Q_개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)
- L R: BL + BL+1 + … + BR-1 + BR 을 출력한다.
Figure 1. 모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정
욱제의 질문에 답하고 함께 엠티를 떠나자!!
입력
첫 번째 줄에 수열 _A_의 길이 _N_과 질문의 개수 _Q_가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)
두 번째 줄에 _N_개의 정수 A1, A2, …, AN 이 공백으로 구분되어 주어진다. Ai 는 수열 _A_의 i 번째 수이다. (1 ≤ Ai ≤ 1,000)
세 번째 줄부터 _Q_개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 L, _R_이 공백으로 구분되어 주어진다. (1 ≤ L ≤ R ≤ N)
주어지는 모든 입력은 자연수이다.
출력
_Q_개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.
예제 입력 1
5 6
2 5 1 4 3
1 5
2 4
3 3
1 3
2 5
4 5예제 출력 1
15
9
3
6
14
9[2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다.
예제 입력 2
5 3
2 5 1 2 3
1 3
2 3
1 5예제 출력 2
5
4
13[2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다.
내 구현
#include <algorithm>
#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)
#define MAX 300001
int P[MAX];
int N, Q;
void solve() {
std::cin >> N >> Q;
P[0] = 0;
for (int i = 1; i <= N; i++) {
std::cin >> P[i];
}
std::sort(P, P + N + 1);
for (int i = 2; i <= N; i++) {
P[i] += P[i - 1];
}
int l, r;
while (Q--) {
std::cin >> l >> r;
std::cout << P[r] - P[l - 1] << '\n';
}
}
int main() {
IO;
solve();
return 0;
}