First,if color \(c\) appears \(x_c\) times in a range,the answer will be add by \(\lfloor \frac{x_c}{2}\rfloor\).

Le’ts sort all the queries and use “sweep line” to solve this problem. It means we iterate \(i\) from \(1\) to \(n\) and answer all the queries such that \(r=i\).

When we increase \(i\) to \(i+1\),let’s call the color of \((i+1)\) -th one is \(c\),we only care all the occurrences of color \(c\) before \((i+1)\).

Le’ts call all the occurrences of color \(c\) (before \((i+1)\)) is \(c_1,c_2,...,c_k\). For all \(j=k-1,k-3,k-5,....,\) We just add \((c_j,c_{j+1}]\) by \(1\). We can use bit to maintain it.

It’s \(O(\sum {x_c^2}\log n\)). It seems to be very slow.

But we know when \((\sqrt{n}\gt x_1,x_2,...,x_n\ge 0 \land x_1+x_2+...+x_n=n)\) ,we can prove that \(\sum_{i=1}^{n}x_{i}^2\le n\sqrt{n}\)。

We set a number \(B\)(B should be a bit larger than \(\sqrt n\)):When \(c_x\lt B\) we use it in “sweep line”,otherwise we just perform an \(O(q\log n)\) brute solution for this color.

Let \(B=2000\) and it will run fast enough.

submission:https://atcoder.jp/contests/abc242/submissions/29885875