便宜のため、与えられた列を \(2\) 個連結した列

\[C' = (C'_1, C'_2, \ldots, C'_{2N}) \coloneqq (C_1, C_2, \ldots, C_{N}, C_1, C_2, \ldots, C_{N})\]

を考え、本問題を \(C'\) の区間 \([l, l+N-1]\) について操作を行うときに箱に入るボールの総数を各 \(l = 1, 2, \ldots, N\) について求める問題と捉えます。 列 \(C'\) の区間 \([l, r]\) に含まれる色 \(c\) のボールの個数を \(f(c, l, r)\) で表し、元の列 \(C\) 全体での色 \(c\) のボールの個数 \(f(c, 1, N)\) を \(g(c)\) で表します。

まず、ある \(1\) つの固定された区間 \([l, l+N-1]\) に対する問題の答えを求めることを考えます。 区間 \([l, l+N-1]\) に対して操作を行った結果、最終的に色 \(c\) のボールで使用される箱が \(b(c, l)\) 個のとき、最終的に箱に入っている色 \(c\) のボールの総数は \(\min\lbrace b(c, l) \times K, g(c)\rbrace\)で あり、求める答え \(\mathrm{ans}_l\) は

\[\mathrm{ans}_l = \sum_{c = 1}^N \min\lbrace b(c, l) \times K, g(c)\rbrace\]

です。 各色 \(c\) の \(b(c, l)\) が分かれば \(\mathrm{ans}_l\) が求まるので、次にこの値について考えます。

空の箱に入れられる（その結果、その色が使用する箱の個数が \(1\) 増える）可能性があるボールは、その色のボールの中で \(1, K+1, 2K+1, 3K+1, \ldots \) 番目に処理されるボールです。 そこで、各色内で\(1, K+1, 2K+1, 3K+1, \ldots\) 番目に処理されるボールをチャンスボールと呼ぶことにします。

チャンスボール（色問わず）が \(1\) 個処理されるたびに空の箱は \(1\) 個ずつなくなっていくので、\(b(c, l)\) は先着 \(M\) 個目までに処理されるチャンスボールの中に含まれる色 \(c\) のチャンスボールの個数と等しいです。 では、ちょうど先着 \(M\) 個目に処理されるチャンスボールの位置はどこでしょうか？

位置 \(l\) から操作を開始するとき、区間 \([l, r]\) までに存在する色 \(c\) のチャンスボールの個数は \(\left\lceil f(c, l, r) / K \right\rceil\) なので、区間 \([l, r]\) までにあるチャンスボールの総数（色問わず）は、

\[S(l, r) \coloneqq \sum_{c = 1}^N \left\lceil \frac{f(c, l, r)}{K} \right\rceil\]

です。 したがって、先着 \(M\) 個目のチャンスボールの位置は、\(S(l, r) \geq M\) を満たす最小の \(r\) で与えられます。 これを \(r_l\) とおくと、\(b(c, l) = \left\lceil f(c, l, r_l) / K \right\rceil\) なので求める答え \(\mathrm{ans}_l\) は

\[ \mathrm{ans}_l = \sum_{c = 1}^N \min\left\lbrace \left\lceil \frac{f(c, l, r_l)}{K} \right\rceil \times K, g(c) \right\rbrace \tag{1} \]

です（ただし、\(S(l, r) \geq M\) を満たす最小の \(r\) が \(r \leq l+N-1\) の範囲に存在しないときは、便宜上 \(r_l \coloneqq l+N-1\) と考えます）。 つまり、\(\mathrm{ans}_l\) を求めるには、\(l\) に対して \(r_l\) を求めて上式 (1) を計算すれば良いです。 しかし、全ての \(l = 1, 2, \ldots, N\) についてそれを愚直に行うのでは、実行制限時間に間に合わせるのは絶望的です。

そこで、上の議論から \(r_1 \leq r_2 \leq \cdots \leq r_N\) となることに注目し、\(l = 1, 2, \ldots, N\) の順に答えを求めていくことにすると、\(l\) を増やしながら各 \(r_l\) をいわゆる尺取法の要領で効率的に求められます。 また、尺取法の過程で、現在見ている区間 \([l', r']\) 内の (1) に対応する値を保持し、\(l'\) や \(r'\) を \(1\) 増減させるたびにこれを随時差分更新することで、各 \(\mathrm{ans}_l\) を全体で \(O(N)\) 時間で求められます。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
using namespace std;

int n, m, k;
int c[400001], all[200001];
int cnt[200001], box[200001], sum, ans;

void add(int i,int x){
	ans -= min(box[i] * k, all[i]);
	sum -= box[i];
	box[i] -= (cnt[i]+k-1)/k;
	cnt[i] += x;
	box[i] += (cnt[i]+k-1)/k;
	sum += box[i];
	ans += min(box[i] * k, all[i]);
}

int main(void){
  cin >> n >> m >> k;
  for(int i = 1; i <= n; i++) cin >> c[i], c[n+i] = c[i], all[c[i]]++;

  int r = 0;
  for(int l = 1; l <= n; l++){
    while(r+1 < l+n && sum < m) r++, add(c[r], 1);
    cout << ans << "\n";
    add(c[l], -1);
  }

  return 0;
}