各クエリの答えは各色のうち（区間内で）一番左のもののみをカウントすることで求まります。

\(d_i\) を、『\(c_i\) よりも左にある同じ色のボールのうち、位置が一番近いもののindex』と定めます（存在しない場合は-1）。こうすれば各クエリの答えは『\(d\) の区間 \([L, R)\) のうち、\(L\) 未満となる要素数』に一致します。

それはWavelet Matrixなどを用いて各クエリ \(O(\log N)\) で高速に求まります。なおWavelet Matrixに負の値をぶち込むとバグるので工夫が必要です。

実装例(C++)

余談ですがこの解法を思いつかないと解けない問題が存在します。