abc344E 维护元素唯一的序列

给定序列A[N]，元素值各不相同，有Q个操作，格式如下：

• 1 x y: 在元素x后面插入元素y，保证插入时x唯一。
• 2 x: 将元素x从序列中删除，保证删除时x唯一。
  输出所有操作完成后的序列。

1<=N,Q<=2E5; 1<=A[i]<=1E9; A[i]!=A[j]

用链表来快速插入和删除，另外还需要map来快速定位，类似LRU的实现。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

const int Z = 200005;
int N, Q;
list<int> lst;
map<int,list<int>::iterator> mp;
void solve() {
    cin >> N;
    rep(i,1,N) {
        int a;
        cin >> a;
        lst.push_back(a);
        mp[a] = --lst.end();
    }
    cin >> Q;
    while (Q--) {
        int op, x, y;
        cin >> op;
        if (op == 1) {
            cin >> x >> y;
            auto it = mp.find(x)->second;
            mp[y] = lst.insert(++it, y);
        } else if (op == 2) {
            cin >> x;
            auto it = mp.find(x)->second;
            lst.erase(it);
            mp.erase(x);
        }
    }
    for (auto i : lst) cout << i << " ";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}