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

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

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

実装例(C++)

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