[ABC344E] Insert or erase 题解

FReQuenter · 2024-03-10 19:03:18 · 题解

特定点插入、删除，考虑链表。

具体地，定义每个数的前驱和后驱。因为值域关系，使用 map 实现。其它就是链表的模板内容，具体可以参考代码。

#include<bits/stdc++.h>
using namespace std;
map<int,int> nxt,pre;
signed main(){
    int n;
    cin>>n;
    int lst=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        nxt[lst]=x;
        pre[x]=lst;
        lst=x;
    }
    int q;
    cin>>q;
    while(q--){
        int op,x,y;
        cin>>op>>x;
        if(op==1){
            cin>>y;
            pre[nxt[x]]=y;
            pre[y]=x;
            nxt[y]=nxt[x];
            nxt[x]=y;
        }
        else{
            pre[nxt[x]]=pre[x];
            nxt[pre[x]]=nxt[x];
        }
    }
    int head=0;
    while(nxt[head]) cout<<nxt[head]<<' ',head=nxt[head];
}