태상이의 훈련소 생활

문제 https://www.acmicpc.net/problem/19951 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 풀이 누적합을 이용해야하는 문제입니다. 1 ≤ N ≤ 100,000 1 ≤ M ≤ 100,000 1 ≤ a ≤ b ≤ N 입력값의 범위가 위와 같아서, 누적합을 이용하지 않고 배열을 일일이 연산할 경우에는 시간 복잡도가 O(N^2)으로 1초의 시간 제한을 넘어가게 됩니다. 그래서 누적합 배열에 모든 숫자를 넣는 것이 아니라, 처음과 끝만 기록합니다. for(int i = 0;i