クエリ \((l,r)\) に対して、求めるべき答えは以下です。

• \(\sum_{i=1}^{N} \lfloor(\) 区間 \([l,r]\) 内で色 \(i\) を着ている人数 \()/2 \rfloor\)

区間 \([l,r]\) に対して何らかの方法でこれを求めたとして、この区間の両端を \(1\) つ追加したり両端のどちらかを削除したりすることを考えます。

• \(A_x\) を区間に追加する場合 : 追加する前の区間で \(A_x\) が奇数個含まれていれば、答えが \(1\) 増加します。
• \(A_x\) を区間から削除する場合 : 削除する前の区間で \(A_x\) が偶数個含まれていれば、答えが \(1\) 減少します。

バケットソートを利用すれば、この区間の伸び縮みは \(1\) 要素あたり \(O(1)\) で対応可能であることが分かります。

これにより、この問題は、 Mo’s algorithm によって解くことができます。
Mo’s algorithm とは、区間をいくつかのブロックに分割し、区間の左端のブロック別に区間たちを分割し、

• ブロック順(左端がより左にあるブロックから順)にクエリを処理する。
• 同一ブロック中では、適切にソートされた順番(例えば、区間の右端が左にあるものから順)でクエリを処理する

というテクニックです。

日本語による解説記事をいくつか示します。
ei1333の日記 - Mo’s algorithm
@ageprocppさんの記事 - Mo’s algorithm(クエリ平方分割)の話

計算量はブロックの個数を \(B\) として \(O(NB + Q(N/B))\) なので、\(B = \Theta(\sqrt{Q})\) とすれば、\(O(N\sqrt{Q})\) になります。
実装例(C++)

類題: Powerful array (Yandex.Algorithm 2011: Round 2)