G - Range Pairing Query Editorial by en_translator
For a query \((l,r)\), what we want is the following:
- \(\sum_{i=1}^{N} \lfloor(\)the number of people in segment \([l,r]\) wearing Color \(i\)\()/2 \rfloor\).
Suppose that we somehow found these value for the segment \([l,r]\). What happens when the segment extends or shrinks by one?
- When \(A_x\) is added to the segment: if there were odd number of \(A_x\)’s in the segment before extended, then the answer increases by \(1\).
- When \(A_x\) is removed from the segment: if there were even number of \(A_x\)’s in the segment before shrank, then the answer decreases by \(1\).
Packet sort enables to respond to the extension/shrink of a single element in an \(O(1)\) time each.
Therefore, this problem can be solved with Mo’s algorithm. Mo’s algorithm is a technique in which the segment is divided into several blocks, the segments are divided into groups depending on which block the left end of each block belongs, then
- queries are processed in the order of blocks (the block with leftmost left end processed first);
- in the same block, queries are processed in a certain sorted order (for example, the block with the leftmost right end processed first).
Here are references written in Japanese.
Diary by ei1333 - Mo’s algorithm
Article by @ageprocpp - Mo’s algorithm(クエリ平方分割)の話
The time complexity is \(O(NB + Q(N/B))\) where \(B\) is the number of blocks. By letting \(B = \Theta(\sqrt{Q})\), it will be \(O(N\sqrt{Q})\).
Sample code (C++)
Similar Problem: Powerful array (Yandex.Algorithm 2011: Round 2)
posted:
last update: