Mo's 알고리즘 최적화 : Snake/지그재그 정렬

Mo's 알고리즘 참 재미있네요.
힐베르트 곡선과 같은 최적화 기법도 있지만
정렬 방법에 따라 상수항이 크게 바뀌어서 속도가 확 줄어들기도 하네요.

간단하게 sort에 한가지 아이디어만 첨부해서 상수항을 줄이는 방법 공유합니다.

---

1. 서론: Mo’s Algorithm에서 “정렬”이 중요한 이유

Mo’s Algorithm은 쿼리 $(L, R)$를 적절한 순서로 처리해, 구간을 나타내는 포인터 $(curL, curR)$의 이동량을 줄이는 기법입니다. 보통 블록 크기를 $B \approx \sqrt{N}$로 잡고,

• $L$을 블록 번호 ($k = \lfloor L/B \rfloor$)로 묶고
• 같은 블록 내에서 $R$ 기준으로 정렬

해 처리합니다. 이때 실행 시간은 “포인터 이동 횟수”에 크게 좌우되므로, 정렬 순서의 상수항 최적화가 실제 성능에 꽤 큰 영향을 주기도 합니다.

---

2. 기본 정렬(Standard Mo Ordering)과 블록 경계 점프

가장 흔한 기본 정렬은 다음과 같습니다.

정렬 기준: (($\lfloor L/sqrtN \rfloor, R$)

N = int(input()) 	# 입력 array의 크기
arr = [0] + list(map(int, input().split()))
M = int(input())	# 쿼리의 개수
Q = []
for i in range(M):
    l, r = map(int, input().split())
    Q.append((l, r, i))
# 일반적인 정렬
Q.sort(key=lambda x: (x[0]//sqrtN, x[1]))

$(curL, curR)$의 탐색은 초록색 점선을 타고 움직입니다.

이 방식도 표준적인 Mo's 정렬로 정상 동작하지만, 블록이 바뀌는 순간에

• 이전 블록의 마지막 쿼리가 큰 $R$에서 끝났는데
• 다음 블록의 첫 쿼리가 작은 $R$로 시작하면

$curR$이 크게 되돌아가야 해서 불필요한 왕복 큰 점프가 발생할 수 있습니다.
(정답/오답과 무관하게 상수항을 키우는 요소)

---

3. Snake-like / Zigzag / Boustrophedon Ordering

이 점프를 줄이기 위한 간단한 상수 최적화가 있습니다.

홀수 블록: $R$ 오름차순
짝수 블록: $R$ 내림차순

이 정렬은 보통 아래 용어로 부릅니다.

• Snake-like ordering
• Zigzag ordering
• Boustrophedon scan/order
• Alternating R-order per block (블록마다 R 정렬 방향 교차)

즉, “타자기처럼 매 줄마다 왼쪽으로 복귀”하는 느낌이 아니라, ㄹ자(지그재그)로 연속 이동하는 경로를 만들려는 아이디어입니다.

sqrtN = int(N**0.5)
Q.sort(key=lambda x: (
    x[0]//sqrtN,
    x[1] if (x[0]//sqrtN) % 2 == 0 else -x[1]
))

교차의 핵심은 % 2 입니다.

---

4. 직관적 해석: Raster Scan vs Boustrophedon Scan

$(L, R)$ 쿼리를 2차원 평면에 찍어 보면,

• 표준 정렬은 블록마다 항상 (R)을 증가시키는 Raster scan(한 방향 스캔) 느낌
• snake-like는 블록마다 방향이 바뀌는 Boustrophedon scan(ㄹ자 스캔) 느낌

이라서, 도표로 비교하면 “블록 경계 점프가 줄어드는 모습”이 훨씬 직관적으로 보입니다.

---

5. Hilbert Order와는 다르다 (용어 주의)

Hilbert order(힐베르트 순서)도 Mo 최적화에서 자주 언급되지만,

• Snake-like 정렬: 블록 단위로 $R$ 정렬 방향만 교차시키는 간단한 휴리스틱
• Hilbert order: $(L,R)$ 점들을 space-filling curve 규칙으로 더 정교하게 방문하는 방법

이라서 Snake-like를 “Hilbert curve”라고 부르진 않는 게 안전합니다.
대신 “Hilbert order처럼 locality를 개선하려는 방향의, 구현이 쉬운 상수 최적화” 정도로 표현하는 게 정확합니다.

---

6. 요약

• 표준 Mo 정렬 $(\lfloor L/B\rfloor, R)$은 기본 해법으로 충분히 유효하다.
• 다만 블록 경계에서 $R$이 크게 되돌아가는 점프가 생겨 상수항이 커질 수 있다.
• Snake-like(Zigzag/Boustrophedon) ordering은 블록 홀/짝에 따라 $R$ 방향을 바꿔, 이런 점프를 줄이는 경향이 있다.

예시 input :

100 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
28
1 2
3 12
6 40
9 95
11 3
14 20
17 60
19 90
21 10
29 90
31 90
39 10
41 10
49 90
51 90
59 10
61 10
69 90
71 90
79 10
81 10
89 90
91 5
92 12
94 18
96 25
98 55
99 98