[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 17069번: 파이프 옮기기 2  (0) 2019.03.15
[BOJ] 11967번: Switching on the Lights  (2) 2019.03.10
[BOJ] 16964번: DFS 스페셜 저지  (0) 2019.03.10
[BOJ] 16994번: 로프와 쿼리  (0) 2019.03.06
[BOJ] 1688번: 지민이의 테러  (0) 2019.03.06
[BOJ] 1956번: 운동  (0) 2019.02.24
  Comments