[ABC344E] Insert or Erase 题解

2c_s · 2024-03-10 12:43:14 · 题解

题目传送门

思路

看到插入、删除操作马上想到链表。又看到数据范围是 1\le A_i,x,y\le 10^9\space(1\le i\le N)，又可以想到用 map 保存。于是本题做法为：用 map 保存的双向链表。

插入操作：下一个点的前驱记录为 y；加入点的前驱为 x，后继为下一个点；最后记录这个点的后继为 x。最后修改 x 的后继防止内存丢失。

删除操作：上一个点的后继记录为下一个点，下一个点的前驱记录为上一个点。

• 可选优化：把 map替换为复杂度更优的 unordered_map。

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,q,a[N];
struct node{
    int head,tail;//head 前驱，tail 后继。
};unordered_map<int,node>mp;
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)a[i]=read();
    mp[0].tail=a[1];//记得保存 0 的后继，查询时用。
    for(int i=1;i<=n;++i){
        mp[a[i]].head=a[i-1];//记录每个点的前驱和后继。
        mp[a[i]].tail=a[i+1];
    }
    cin>>q;
    while(q--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            int k;
            cin>>k;
            mp[mp[x].tail].head=k;
            mp[k].head=x;
            mp[k].tail=mp[x].tail;
            mp[x].tail=k;//最后改。
        }
        else{
            mp[mp[x].head].tail=mp[x].tail;
            mp[mp[x].tail].head=mp[x].head;
            mp[x].head=mp[x].tail=0;
        }
    }
    int k=mp[0].tail;
    while(k){
        cout<<k<<" ";//从第一个点一直输出。
        k=mp[k].tail;
    }
    return 0;
}

AC 记录