ABC344E 题解

_Weslie_ · 2024-03-10 09:27:39 · 题解

思路

由题面我们容易联想到链表。

但是我们显然不能直接写个链表，因为这样不仅不好查找，而且写起来也不方便。

这时我们就要使用 map，设 mp_i 表示 i 的后一个数（即后缀）。

同理 pre_i 表示 i 的前缀。

i 表示的是数字，不是下标！

代码实现

为什么要记录 pre？因为这样在删除时可以 \operatorname{O}(1) 删除，否则需要在队伍中查找后删除，时间复杂度劣。

同时，如果删除的是第一个元素，要将队头进行修改。

Code

#include<iostream>
#include<map>
using namespace std;
map<int,int>mp;
map<int,int>pre;
int q,n,head;
int a[200005];
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
        mp[a[i-1]]=a[i];
        pre[a[i]]=a[i-1];
    }
    head=a[1];
    cin>>q;
    while(q--) {
        int opt,x,y;
        cin>>opt>>x;
        if(opt==1) {
            cin>>y;
            mp[y]=mp[x];
            pre[y]=x;
            pre[mp[y]]=y;
            mp[x]=y;
        } else {
            if(head==x) {
                y=mp[x];
                mp[pre[x]]=y;
                pre[y]=pre[x];
                head=y;
            } else {
                y=mp[x];
                mp[pre[x]]=y;
                pre[y]=pre[x];
            }
        }
    }
    int _=head;
    while(mp[_]!=0) {
        cout<<_<<' ';
        _=mp[_];
    }
    cout<<_;
    return 0;
}