[BOJ] 16993번: 연속합과 쿼리

https://www.acmicpc.net/problem/16993

맨 처음 문제를 보고 하룻동안 생각했는데 전혀 감을 못잡았습니다. 그러다가 슬랙 qna에서 얘기 나누는 것을 듣고 풀이를 귀동냥으로 얻어서 풀어냈습니다.

핵심 아이디어는 segment tree를 구성해 {구간 내에서 최대 합, 가장 왼쪽의 원소를 포함한 최대 합, 가장 오른쪽의 원소를 포함한 최대 합}을 원소로 가지게끔 합니다. 그러고난 뒤에 주어진 쿼리를 최대 $lgN$개의 구간으로 쪼개 처리하면 됩니다. 구간을 합치는 과정은 잘 생각해보면 $O(1)$에 해결 가능하기 때문에 시간복잡도는 $O((N+M)lgN)$입니다.

https://github.com/blisstoner/BOJ/blob/master/16993.cpp