unordered_map이 PS하는 블로그

수쿼 스타일의 문제를 보다보면 특정 구간에 등차수열을 더하거나, 피보나치 수열을 더하는 등의 문제를 볼 수 있다. 이 문제를 통해 등차수열에 관한 쿼리는 어떻게 처리하는지 익혀보길 바란다. 그리고 다이아라고 되어있긴 한데 왜 다이아인지 전혀 모르겠다. 플1 정도가 적당해보이고, 사람에 따라 더 내려서 생각할 수도 있을 것 같다. 푸른색 티어에 겁먹지 말고 도전해보자. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j x y : 구간 [i, j]에 초항이 x이고 공차가 y인 등차수열 더하기 2 i j : 구간 [i, j]에 포함되는 등차수열인 구간 [l, r] 중 가장 긴 것의 길이를 출력 사용 알고리즘 금광 세그 풀이 태그에 레이지가 달려있긴 한데 사실 레이지가 필수적이..

금광 세그를 연습하기에 매우 좋은 문제이다. 개인적으로 처음에는 아이디어 떠올리는 것이 어려웠기 때문에 풀이를 조금 읽다가 아이디어가 잡히면 남은 풀이는 혼자 완성해보는 것을 추천한다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. x1 y1 x2 y2 : 구간 [x1, y1]에 속하는 모든 i와 구간 [x2, y2]에 속하는 모든 j(>=i)에 대해서 수열의 [i, j] 구간합의 최댓값을 출력한다. 사용 알고리즘 금광 세그 풀이 금광 세그를 구현하면 임의의 구간 [i, j]에서 수열의 prefix 최대합, suffix 최대합, 부분 최대 합, 전체 합을 O(logN)에 구할 수 있다. 각 값을 구간의 left, right, ans, all이라고 하자. ① [x1, y1]과 [x2, ..