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)