[일반] 코포 Div3 문제 해답지 질문

[ㅁㄴㅇ(211.59)]

http://codeforces.com/contest/1108/problem/E1

이건데

이거 해답지에

직관적인 방법의 시간복잡도는 n * n * m 나오고

구간합을 쓰면 n * (n + m) 이 나온다는데

구간합을 어떻게 적용시켜야됨?

[시아닌(kimjg1119)]

a부터 b까지에 1을 빼고 싶으면 새로운 배열을 하나 만들어서 a에 1을 빼고 b+1에 1을 더한다음 마지막에 부분합 한번 돌려주고 업뎃해주면됨

[ㅁㄴㅇ(211.59)]

ㄳ