쿼리를 특정 순서로 정렬해서 쿼리 자체를 처리하는 시간을 전체적으로 줄이는 방법이 있기는 합니다. 이렇게 쿼리를 순서대로 보지 않고 원하는 순서대로 처리하는 방법을 쿼리를 오프라인으로 처리한다고 합니다. 32963번 문제를 보면 두 가지 풀이가 있는데요, 첫번째는 최댓값을 찾는 O(N) 과정을 이분탐색으로 O(logN) 으로 바꾸는 방법이고요, 두번째는 사과들을 맛 순서대로 정렬한 후 p 가 큰 쿼리부터 순서대로 답하면 계속 최댓값을 갱신해주며 쿼리 자체는 O(1) 에 처리할 수 있습니다. (투 포인터를 이용하면 총 N개의 사과들을 한번씩 확인하기 때문)

b2r 7달 전
쿼리가 난이도에 미치는 영향이 엄청난가요? 연속합이라는 문제의 티어가 실버였던거 같은데 연속합 + 쿼리를 하니까 플레1이 됬었습니다
쿼리를 처리하기 위해서 만약 O(N)짜리 코드가 있었다면 O(logN)으로 최적화하는 방법 이외의 방법은 없나요? 쿼리를 처리할때 O(Q)가 항상 곱해지는데 O(Q)를 O(logQ)로 최적화 한다던가 그런건 불가능한가요?