ABC344E

spacebar · 2024-03-10 13:16:48 · 题解

这题要求我们在某个数字后面插入数字或删除某个数字，很容易想到链表。

不过正常的链表没法记录每个数的位置，要额外记录。

剩下的就是正常的链表操作了。

注意数组要开大，因为可能会插入更多数。

#include<bits/stdc++.h>
using namespace std;
int nxt[400010];
int lst[400010];
long long num[400010];
map<long long,int>pl;
int np;
int n,q;
int fr=1;
int cnt;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>num[i];
        pl[num[i]]=i;
        nxt[i-1]=i;
        lst[i]=i-1;
    }
    np=n;
    cin>>q;
    int val;
    long long aa,bb,aap;
    fr=1;
    cnt=n;
    while(q--){

        cin>>val;
        if(val==1){
            cnt++;
            cin>>aa>>bb;
            np++;
            aap=pl[aa];
            pl[bb]=np;
            num[np]=bb;
            lst[np]=aap;
            nxt[np]=nxt[aap];
            nxt[aap]=np;
            lst[nxt[np]]=np;
        }else{
            cnt--;
            cin>>aa;
            aap=pl[aa];
            if(fr==aap){
                fr=nxt[aap];
            }
            pl[aa]=0;
            nxt[lst[aap]]=nxt[aap];
            lst[nxt[aap]]=lst[aap];
        }
    }
    int tp=fr;
    while(cnt){
        cout<<num[tp]<<" ";
        tp=nxt[tp];
        cnt--;
    }
    return 0;
}