\(C_k\) は、候補者 \(k\) の最初の得票数とします。

候補者 \(k\) が辞退したとき、当選する候補者は次のように求められます。

1. \(A_i=k, B_i=l\) となっている各 \(i\) に対し、\(C_k\) を \(1\) 減らし、 \(C_l\) を \(1\) 増やす。
2. \(C_i\) が最大となっているような \(i\) （同じものが複数あれば最小）を取得する。
3. 最後に \(C_i\) を元通りにする； \(A_i=k, B_i=l\) となっている各 \(i\) に対し、\(C_k\) を \(1\) 増やし、 \(C_l\) を \(1\) 減らす。

ここで、 \(A_i = k\) であるような \(i\) を \(k\) ごとに前もって列挙しておく（バケットソートに近いやり方）ことで、1. と3. については合計で \(O(N)\) で処理できます。具体的には、バケツ \(1, 2, \cdots, k\) を用意し、人 \(i\) に対してバケツ \(A_i\) に \(i\) を追加しておきます。候補者 \(k\) が辞退したときは、バケツ \(k\) に含まれる人をすべて見ればよいです。

問題は、2. において、 \(C_i\) が最大となっているような \(i\) を取得するために、愚直には毎回 \(O(N)\) 時間かかることです。これにより、全体で \(O(N^2)\) 時間かかり、実行時間制限オーバーとなります。

公式解説では、探索する対象を絞ることで、合計 \(O(N)\) 時間で解決しています。しかし、このパートは適切なデータ構造を用いることで高速に処理することができます。

解法1. std::set など平衡二分探索木

配列 \(C_k\) とともに平衡二分探索木（C++なら std::set） に \((C_k, -k)\) を乗せます。 \(C_k\) が更新されたときはstd::setの中身も更新します。

std::set の最大要素を取得すれば、得票数が最大で、同数なら番号が最小の候補者を求められます。

時間計算量は \(O(N \log N)\) です。

実装例（C++, 323ms） https://atcoder.jp/contests/abc483/submissions/80693614

解法2. セグメント木

配列 \(C_k\) とともに、各候補者 \(k\) に対応する位置に \((C_k,-k)\) を持つセグメント木を構築します。演算はペアの辞書順での max とします。同じく、 \(C_k\) が更新されればセグメント木の対応する位置も更新します。

セグメント木の全体取得をすれば、得票数が最大で、同数なら番号が最小の候補者を求められます。

時間計算量は \(O(N \log N)\) です。

実装例（C++,135ms） https://atcoder.jp/contests/abc483/submissions/80693703