CFR 637 B. Chat Order ( Ad hoc, Set )

Problem - B - Codeforces

題意：
給通知的順序，若是新的人的通知則會到訊息版最上面，否則會將舊的人提到訊息版的最上面。求最終樣貌。

數據範圍：
通知數 1 ≤ N ≤ 2e5
通知的人名 1 ≤ | name | ≤ 10

解法：
在動態過程中，每個人名一定只會對應到一個位置，因此用 map 記錄對應關係。用 set 記錄動態訊息表，第一關鍵字負責排序順位，動態維護 map 更新 set 即可。

時間 / 空間複雜度：
O( | name | N lg N )

int N;
vs notif;

void init(){
    cin >> N;
    notif = vs( N );
    for( int i = 0; i < N; ++i )
        cin >> notif[ i ];
}

set< pair< int, string > > board;
map< string, int > pri_notif;

void preprocess(){
    for( int i = 0, pri = 0; i < N; ++i, ++pri ){
        if( not pri_notif.count( notif[ i ] ) )
            board.emplace( pri_notif[ notif[ i ] ] = -pri, notif[ i ] );
        else
            board.erase( make_pair( pri_notif[ notif[ i ] ], notif[ i ] ) ),
            board.emplace( pri_notif[ notif[ i ] ] = -pri, notif[ i ] );
    }
}

void solve(){
    for( auto pis : board )
        cout << pis.second << endl;
}