공부공간

https://www.acmicpc.net/problem/1306 1306번: 달려라 홍준 첫째 줄에는 뛰는 코스의 길이, 즉 칸수 N과 홍준이의 시야의 범위 M이 주어진다. 시야가 M이라고 하면 현재 위치에서 앞뒤로 M-1칸까지 광고판이 보이는 것이다. (1 ≤ M ≤ N ≤ 1,000,000) 두 번째 www.acmicpc.net 길이가 N인 수열에서, 내가 현재있는 index 에서 [index-(M-1) , index+(M-1)] 에서 가장 큰 값을 찾으면 된다. N = 100만 이므로, N^2의 풀이보다는 NlogN의 풀이인 세그먼트 트리를 이용하여, N개의 쿼리를 처리해주자, 위문제는 O(NlogN+N) 에 처리가 가능하다. 즉, 구간의 최댓값을 저장하는 배열을 세그먼트 트리로 만들면 된다. i..