Mo's Algorithm Movement Cost

Problem

Mo's algorithm sorts offline queries to reduce pointer movement. Sort queries by (l // block, r ascending when the block is even and r descending when it is odd); ties keep the original order because the sort is stable. Starting from left = 0 and right = -1, the cost is the sum of |l - left| + |r - right| measured before each query. Return the total cost. Assume queries are valid and block >= 1.

Hint

The parity trick makes the right pointer sweep back across the array instead of jumping home each block.

Test cases

case 1

in: [8,[[0,3],[2,5],[4,7],[1,6]],3]

expected: 14

case 2

in: [10,[[0,9],[1,2],[4,6],[7,8]],4]

expected: 25

case 3

in: [5,[[0,0],[1,1],[2,2],[3,3],[4,4]],2]

expected: 13

Starter codePython

def mo_movement_cost(n, queries, block):
    # Your code here
    pass

3 test cases · run your code against them in the editor