题解

aeaf · 2024-03-10 10:23:44 · 题解

第一次写题解，写的不太好轻喷

首先题目给出重要信息所有数只出现一次，且给出删除和插入操作，故考虑链表进行维护

因为所有数只出现一次，所以我们可以根据这个数来找到它的 next 和 pre 。

于是剩下的就是链表的基本操作啦

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define next nxt
int n;
map<int,int> next,pre;
int head=1e10;
int a[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    a[0]=head;
    next[head]=a[1];
    for(int i=1;i<n;i++){
        next[a[i]]=a[i+1];
        pre[a[i]]=a[i-1];
    }
    next[a[n]]=INT_MAX;
    pre[a[n]]=a[n-1];
  //构建链表，写的有点累赘
    int Q;
    cin >> Q;
    while(Q--){
        int op;
        cin >> op;
        if(op==2){
            int x;
            cin >> x;
            next[pre[x]]=next[x];
            pre[next[x]]=pre[x];
        }else{
            int x,y;
            cin >> x >> y;
            next[y]=next[x];
            pre[y]=x;
            pre[next[x]]=y;
            next[x]=y;
        }
    }
    while(next[head]!=INT_MAX){
        cout <<next[head]<<" ";
        head=next[head];
    }

    return 0;
}