Introduction to Mo's Algorithm
Range Mode Query: http://zerojudge.tw/ShowProblem?problemid=b417
Given N numbers, M queries for ( ql, qr ), output the maximum frequency and the count of the maximum frequency in range [ ql, qr ] of the N numbers.
( 1 <= N <= 1e5, 1 <= M <= 1e6 )
For these kind of problems that do not require instant answer for each query, where update can be made in O( 1 ) or perhaps O( lg N ), such as from [ l, r ] to [ l, r + 1] or so, Mo's algorithm is a great option.
Let's see about RModeQ, noticing that in a range [ l, r ], having the max frequency, the frequency of each number, and the count of each frequency, is enough to answer a query, and we are able to move to [ l, r + 1 ] by O( 1 ) operation on these values, we could tackle this problem by this offline method.
The essence of this algorithm, can be explained by abstracting these queries to points on a 2D plane. For simplicity, let N = number of queries = the amount of numbers in the given array. Now put these queries in a 2D plane, according to its [ l, r ] value for its coordinate, we would realize that, having the cost of moving from point ( x1, y1 ) to another point ( x2, y2 ) be O( 1 ) * ( | x1 - x2 | + | y1 - y2 | ), the minimum number of steps to traverse all the points would be the complexity of this algorithm.
Let B = sqrt( N ), split these queries into B blocks of size B, sort by each query's left bound to assign each of its block it should belong to, then sort by each right bound in each block. The overall complexity would become around O( n ^ 1.5 ).
Here are some links that I would like to look at sometime later:
