AtCoder Beginner Contest 170, E : Smart Infants

問題文

　https://atcoder.jp/contests/abc170/tasks/abc170_e

問題概要

　$N$ 人の競技プログラマがいて，相異なる $1$ から $N$ の整数で番号付けされている．また，組織が $2 \times 10^5$ あり，同様に $1$ から $2 \times 10^5$ で番号付けされている．人 $i$ のレートは $A_i$ である．
　これから $Q$ 回の転属が行われ，$j$ 回目の転属では人 $C_j$ が組織 $D_j$ に転属する．それぞれの転属後について，競技プログラマが一人以上いる組織全てに渡って組織内のレートの最大値をとった集合の最小値を求め，出力せよ．

制約

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $C, B, D$ が意味的に妥当になるいい感じの制約（原文参照＞＜；）

解法

　答えの計算方法が問題文に書かれているので，ある程度高速に転属をシミュレートできれば問題を解くことができます．$N, Q$ の制約から考えると，要素の追加・削除・最大値/最小値の問い合わせを $O( \log N )$ 時間程度で処理できるデータ構造があれば，制限時間に間に合います．C++ の場合，std::multiset が利用できます．
　具体的にシミュレートの手順を考えます．必要な multiset は複数あって，まず，各組織ごとに所属する競技プログラマのレーティングの一覧を管理する multiset が必要です．また，答えを出力するために，競技プログラマがいる組織ごとの Highest レートをまとめた一覧が一つ必要です．組織ごとの Highest レートの更新は，人の転属前に当該組織の Highest レートを削除してから転属後に当該組織の Highest レートを追加することで，処理を一元化できます．
　……，と考えた上で，人が転属するときにやるべきことは

1. 転属前の組織の Highest レートを，Highest レートの一覧から削除する
2. 転属前の組織から，転属する人のレートを削除する
3. 転属前の組織に競技プログラマが残っていれば，組織内の Highest レートを Highest レートの一覧に追加する
4. 転属先に競技プログラマがいれば，Highest レートの一覧から転属先の Highest レートを削除する
5. 転属先のレート一覧に転属する人のレートを追加する
6. Highest レートの一覧に転属先の組織の Highest レートを追加する
7. 転属する人の現在の所属を更新する

となります．このように列挙すると煩雑に見えますが，1, 2, 3 と 4, 5, 6 は逆順で対になるような感じになっていることに注意するとやや見通しがよくなります．この更新をした後に，Highest レートの一覧から最小値をとってきて出力すればよいです．
　計算量としては，multiset の初期状態の作成時に $N$ 回の multiset 操作が必要で，その後転属ごとに multiset の操作を定数回ずつ行うので，$O( ( N + Q ) \log N )$ 時間となります．

コード

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );
	cout << setprecision( 12 ) << fixed;

	IN( int, N, Q );
	VI A( N ), B( N );
	REP( i, N )
	{
		cin >> A[i] >> B[i];
	}

	multiset< int > highests;
	static multiset< int > ratings[ 1 << 18 ];

	REP( i, N )
	{
		ratings[ B[i] ].insert( A[i] );
	}
	REP( i, 1 << 18 )
	{
		if ( !ratings[i].empty() )
		{
			highests.insert( *rbegin( ratings[i] ) );
		}
	}

	REP( Q )
	{
		IN( int, C, D );
		--C;

		const int now = B[C];
		const int rating = A[C];

		highests.erase( highests.find( *rbegin( ratings[ now ] ) ) );
		ratings[ now ].erase( ratings[ now ].find( rating ) );
		if ( !ratings[ now ].empty() )
		{
			highests.insert( *rbegin( ratings[ now ] ) );
		}

		if ( !ratings[D].empty() )
		{
			highests.erase( highests.find( *rbegin( ratings[D] ) ) );
		}
		ratings[D].insert( rating );
		highests.insert( *rbegin( ratings[D] ) );

		B[C] = D;

		cout << *begin( highests ) << '\n';
	}
	cout << flush;

	return 0;
}