left, right 범위를 넓히거나 좁히는 연산의 시간복잡도를 O(T(N))으로 두겠습니다. 작성하신 코드에서는 O(logN)입니다. mo's 알고리즘의 시간 복잡도는 O((N+M)sqrt(N)T(N))입니다.
문제의 제한을 대입해서 계산해보면 작성자님 코드는 대략 20억 정도 나오는데 1초에 1억 정도의 연산을 한다고 가정하면 20초가 걸립니다. 따라서 시간 초과가 뜨는 것입니다.
---
힌트를 드리자면, 보통 mo's 알고리즘의 N, M 제한은 (100'000, 100'000), (200'000, 200'000)인데, 이 문제는 (300'000, 10'000)으로 다소 특이한 편입니다. O((N+M)sqrt(N)logN) 시간복잡도는 안되고 O((N+M)sqrt(N))까지만 가능합니다. 따라서 O(T(N))을 O(1)에 수행되도록 하는 방법을 생각하여야 합니다. 색깔 범위가 작다는 점을 이용하면 O((N+M)sqrt(N) + M*C) 혹은 O((N+M)sqrt(N) + Msqrt(C))에 해결하실 수 있습니다.

sk14cj 11달 전
현재 제가 접근한 로직은 다음과 같습니다.
1. Mo's 알고리즘을 이용해서 쿼리를 빠르게 처리해줍니다.
2. 색깔의 개수를 빠르게 업데이트하기 위해 이분탐색을 이용합니다.
3. 이분탐색의 로직은 다음과 같습니다. (color = arr[left] 혹은 arr[right])
4. right < j에서는 cnt[color]보다 큰 cnt[target] 중 가장 낮은 순위(혹은 가장 랭크값이 높은)를 찾아서 target에 넣어줍니다.
5. target += 1 처리를 통해서 target = (cnt[color]와 같은 개수를 가진 색깔 중 가장 랭킹이 높은(혹은 랭킹값이 작은) 인덱스)로 처리합니다.
6. target순위를 가진 색깔 other와 color의 순위 정보를 교환해줍니다.
7. cnt[color] += 1을 해줍니다. 이럴 경우, 같은 개수의 색깔 중 순위가 가장 높은 랭크를 얻었기에, +1 처리를 해줘도 랭크값이 옳다고 생각했습니다.
8. right > j, left < i, left > i에서는 상황에 따라 이를 반대로 적용해주었습니다.
저의 접근 자체가 잘못되었는지, 혹은 접근 자체는 옳지만 구현에서 문제가 있는지 궁금합니다. 감사합니다.