Mo's 알고리즘(구간 질의 정렬) 계산기

구간 질의를 미리 다 받아 놓고 「영리한 순서」로 정렬해 처리하는 방법입니다. 현재 구간 [L,R]에서 다음 질의 [l,r]로 옮기는 비용이 |L−l|+|R−r|이므로, 비슷한 질의끼리 이웃하게 정렬하면 총 이동이 O((n+q)√n)로 떨어집니다.

왼쪽 끝 l이 속한 √n 크기 블록으로 먼저 정렬하고, 같은 블록 안에서는 오른쪽 끝 r로 정렬합니다. 두 줄짜리 비교자가 전부입니다.

왼쪽 포인터는 한 블록 안에서 블록 폭(√n) 안에서만 움직이므로 질의마다 √n, 합쳐서 O(q√n)입니다. 오른쪽 포인터는 한 블록 안에서 r이 단조증가라 총 n칸만 움직이고 블록이 √n개이므로 O(n√n)입니다.

짝수 블록은 r 오름차순, 홀수 블록은 r 내림차순으로 정렬하는 개선입니다. 블록이 바뀔 때 오른쪽 포인터가 배열 끝에서 앞으로 되돌아오는 낭비가 사라져 실측 이동이 대개 30% 안팎 줄어듭니다. 정렬 비교자 한 줄을 고치는 것치고 큰 이득입니다.

구간을 한 칸 넓히거나 좁히는 것이 O(1)에 되어야 합니다. 서로 다른 값의 개수, 같은 값 쌍의 개수, 구간 XOR 빈도 같은 것은 됩니다. 구간의 중앙값처럼 한 칸 갱신이 O(1)이 아닌 것은 그대로 쓸 수 없습니다.

쓸 수 없습니다. 질의를 미리 다 알아야 순서를 바꿀 수 있기 때문입니다. 질의가 하나씩 들어오고 즉시 답해야 한다면 세그먼트 트리나 다른 자료구조를 써야 합니다.

질의 수가 배열 크기와 비슷해질 때부터입니다. 질의가 아주 적으면 정렬 비용이 더 클 수도 있습니다. 그리고 여기서 세는 것은 이동 횟수일 뿐이라, 실제 수행시간은 한 칸을 더하고 빼는 비용까지 곱해야 나옵니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.