제곱근 분할법. [13546]

[1. 문제 설명]

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

---

[2. 풀이 접근]

완전 탐색으로 풀이

• L -> R 방향으로 배열을 순회하면서
• 배열의 값을 index 로 하여 배열의 값의 최초 출현 위치를 기록하고,
• 2회 이상 출현 시, 최초 저장 된 위치를 이용하여 구하고자 하는 길이를 계산 하고,
• 필요 시, 전체 결과를 갱신하도록 한다.

완전 탐색 풀이는 배열의 길이와 쿼리의 개수로 보아 그 시간 복잡도는 O(NK) 이고,

N 과 K 모두 최대 100,000 이므로, 시간 조건을 만족하지 못함.

 

여기서, 배열 내 값이 변하지 않고 현재 쿼리의 결과가 나중 쿼리 결과에 영향을 주지 않으므로 

오프라인 알고리즘 적용을 고려해 볼 수 있다.

 

오프라인 알고리즘으로 풀이

• 제곱근 단위로 배열을 분할 및 mo`s 알고리즘을 적용하여 각 쿼리를 정렬하도록 한다.
• 현재 쿼리에서 배열 내 같은 값의 위치 차 (이하 거리) 의 발생 횟수를 저장 할 배열(dists) 을 명시한다.
  # index 는 거리 (거리의 최대 값은 100,000 이므로 메모리를 할당 할 수 있음)
  # value 는 거리의 발생 횟수
• 즉, 이 배열에서 0 보다 큰 값을 같는 것 중 index 값이 제일 큰 것이 현재 쿼리의 답이 된다.
• 그러나, 최대 값을 찾기 위해 단순히 뒤에서 앞으로 순회하는 경우 전체 배열을 순회해야 하는 경우가 발생 할 수 있다.
• 거리를 적절한 단위로 묶어서(이하 bucket) 생각 할 필요가 있다. (제곱근 분할법을 적용하도록 한다.) (buckets)
• 각 bucket 은 위에서 언급한 배열과 같은 성질을 같는다.
  # index 는 (거리 / 제곱근), 제곱근이 10 이라면 거리가 0 ~ 9 까지가 한 블록으로 묶이는 것이다.
  # value 는 발생 횟수
• 즉, 쿼리의 답은 배열 buckets 와 dists 을 이용해 찾을 수 있다.
• 최대값을 찾아야 하므로, 마지막 bucket 부터 첫번째 bucket 까지 역순으로 순회한다.
• bucket 내 값이 0보다 큰 경우 이 bucket 에서 최대 거리를 찾도록 한다.

특정 bucket 에 해당하는 거리를 dists 에서 역순으로 조회할 때 주의 할점은

시작 index 를 (다음 bucket - 1) 로 설정 후 배열 접근 시 오버플로우가 발생 할 수 있음이다.

왜냐하면

• sqrt(100,000) = 316 (정수 단위만)
• 가장 마지막 bucket 의 값이 0보다 클 때, 그 다음 bucket 은 317*316 으로 100,172 이다.
• 즉, 100,000 보다 커지므로, dists 배열을 이 값보다 약간 크게 잡도록 한다.

---

[3. 코드]