[Silver III] 이건 꼭 풀어야 해! - 17390

[Silver III] 이건 꼭 풀어야 해! - 17390 (누적합)

문제 링크

성능 요약

메모리: 63208 KB, 시간: 796 ms

분류

누적 합(prefix_sum), 정렬(sorting)

문제 설명

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 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개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

처음에 그냥 인덱스를 슬라이싱해서 sum함수를 사용했더니 시간초과가 떴다. 누적합을 이용한 문제였다. 풀이를 참고했는데 생각보다 간단했다. 연속된 합을 구해놓고, 첫 인덱스부터 시작이 아닐시 전체에서 바로 전 인덱스(전 누적합)까지 빼주면 답을 도출할 수 있었다.