各カードがどの山にあるか、あるいは各山のカードの集合を常に管理しながら計算することを目指すと、\(1\) 回の操作で変更するべき量が多くなるため実行時間に間に合わせることは難しくなります。

常に山にあるカードの枚数を高速に取得できる必要はなく、すべての操作を終えた後のみに各山のカードの枚数を取得できればよいことに注意して、各操作において変更するべき量が少ないようなデータを管理しましょう。

状況を簡潔にするために山 \(i\) の一番下に仮想的に動かないカード \(N + i\) があると見なすことにします（このような工夫をせずとも管理するデータの形を少し変えれば計算はできますが、簡潔な方法の一つになっていると考えられます）。

すると、例えば以下のようなデータを管理することにより高速な計算が行えます。

• \(up_i\) : カード \(i\) のすぐ上にあるカード（なければ \(-1\)）
• \(down_i\) : カード \(i\) のすぐ下にあるカード（なければ \(-1\)）

\(i\) 回目の操作の際には \(D_i = down_{C_i}\) とおくと、以下のように管理するデータを更新すれば十分です。

• \(down_{C_i}\) を \(P_i\) に置き換える
• \(up_{P_i}\) を \(C_i\) に置き換える
• \(up_{D_i}\) を \(-1\) に置き換える

答えを取得する際には、各 \(i\) についてカード \(N + i\) から \(up\) を辿っていけばよいです。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	vector<int> up(2 * n, -1), down(2 * n, -1);
	for (int i = 0; i < n; i++) up[n + i] = i, down[i] = n + i;
	while (q--) {
		int c, p;
		cin >> c >> p;
		c--; p--;
		int d = down[c];
		down[c] = p;
		up[p] = c;
		up[d] = -1;
	}
	for (int i = 0; i < n; i++) {
		int x = n + i, ans = 0;
		while (up[x] != -1) {
			x = up[x];
			ans++;
		}
		cout << ans << " \n"[i == n - 1];
	}
}