コンテスト後，公式解説に「multisetなどを用いることで高速に処理することができます」ってあったからPythonじゃ解けないのか？？と放置していた問題．2時間くらいかかっちゃったけど，なんとかC++で解けた．

解法

シミュレーションをする．

各幼稚園ごとの幼児のレートのmultisetと，幼児 $i$ をキーとし，その幼児のレートと幼稚園のpairを要素としたmapと，また各幼稚園の一番レートの高い幼児を最強園児と呼ぶが，最強園児のレートのmultiset $top$ を用意する（最後だけ説明の都合上，名前をつけた）．

各クエリにおいて，幼児 $c$ のレートを $a$ ，転園前の幼稚園を $b$ ，転園後の幼稚園を $d$ とする．やることは以下の通り．

転園前の幼稚園 $b$ の最強園児のレートを $top$ から削除する
転園処理の消去部分を行う
もし転園前の幼稚園 $b$ にまだ幼児がいれば，転園前の幼稚園 $b$ の最強園児のレートを $top$ に挿入する
もし転園後の幼稚園 $d$ に幼児がいれば，転園後の幼稚園 $d$ の最強園児のレートを $top$ から削除する
転園処理の挿入部分の処理を行う
転園後の幼稚園 $d$ の最強園児のレートを $top$ に挿入する

実装の注意は，multisetから要素を消すときは，単純にeraseをするとすべて消えてしまうこと．

multiset<int> top;
top.insert(10);
top.insert(10);
top.erase(10); // 10が二つとも消える

一つだけ消したいときは，

multiset<int> top;
top.insert(10);
top.insert(10);
auto it = top.find(10);
if (it != top.end()) {
    top.erase(it);  // 10が一つだけ消える
}

とするといいらしい（下のACコードでは面倒なのでif文のところを書いていない）．

あと初めてのmultisetだったので知らなかったが，

*top.begin();  // 最小値
*top.rbegin();  // 最大値

らしい．

追加サンプル1

追加サンプル2

出力は全部10になる．

コード

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
using namespace std;
using ll = long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

constexpr int INF = 1e9 + 7;
constexpr int _MAX = 200005;
/* -------------------------------------------------- */

void solve() {
    V<multiset<int>> T(_MAX);     // 園b : レートa
    map<int, pair<int, int>> mp;  // 幼児i : レートa, 所属園b
    multiset<int> top;            // 最強園児のレートの多重集合
    int n, q;
    cin >> n >> q;
    rep(i, n) {
        int a, b;
        cin >> a >> b;
        --b;
        T[b].insert(a);
        mp[i] = {a, b};
    }
    rep(i, _MAX) {
        if (!T[i].empty()) {
            int v = *T[i].rbegin();  // 園iのレートの最大値
            top.insert(v);
        }
    }

    int ans = *top.begin();  // 最強園児のレートの最小値
    int c, d;
    while (q--) {
        cin >> c >> d;
        --c;
        --d;
        auto [a, b] = mp[c];
        mp[c] = {a, d};

        int v = *T[b].rbegin();    // 園bの最強園児のレート
        top.erase(top.find(v));    // いったん消す
        T[b].erase(T[b].find(a));  // 転園処理（消去）
        if (!T[b].empty()) {
            v = *T[b].rbegin();  // 園bの最強園児のレート
            top.insert(v);
        }

        if (!T[d].empty()) {
            v = *T[d].rbegin();      // 園dの最強園児のレート
            top.erase(top.find(v));  // いったん消す
        }
        T[d].insert(a);      // 転園処理（挿入）
        v = *T[d].rbegin();  // 園dの最強園児のレート
        top.insert(v);

        ans = *top.begin();
        cout << ans << "\n";
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

提出コードへのリンク

Pythonだとheapqを幼稚園の数くらい生やしてる人とかいたっぽい．

今日知ったこどふぉ豆知識コーナー

から

f:id:ntk_ta01:20201111014250p:plain

フレンドのコドフォのAC数一覧が見られる！自分は今123AC．え　もっと増やしてえ～AC数の近いフレンドに負けません．今AC数が負けているフレンドもできるだけたくさん抜かしたいです．

ntk log ntk

競プロや非競技プロのやったことを書いています.

ABC170 E - Smart Infants

解法