[ABC344E] Insert or Erase 题解

· · 题解

六个字：难想，难写，难调

我们一看插入和删除就知道用链表，可是现在几乎没有人用链表 （我忘了） ，于是我就用数组模拟指针，定义 l 数组存这个数左边是哪个数，r 数组存这个数右边是哪个数。

初始化不必多说，就在最后用 r 数组存上 -1145。

根据链表的原理，我们要添加一个数，就是让这个数前面后面的链改变一下，就像下图

根据此图，我们可以修改一下我们的数组。

l_5=1 l_4=5 r_1=5 r_5=4

这一部分写成代码较为困难，涉及到许多转化，自己在草稿纸上手写几遍再多看看代码就明白了。

 if(op==1){
      cin>>x>>y;
      l[r[x]]=y;
      l[y]=x;
      int d=r[x];
      r[l[y]]=y;
      r[y]=d;
}

删除相对简单一点，我们只需要把连着要删除数字的链连上前面的或后面的。 这样说可能不清楚，可参考下图,再看看代码就能理解。

 else{
    cin>>x;
    int L=l[x];
    int R=r[x];

    l[R]=l[x];
    r[L]=r[x];

}

最后就是输出了，我们在 r 的最后放了一个 -1145，就是为了输出什么时候到达终点。

 int tot=0;
    while(r[tot]!=-1145){
        //cout<<tot<<" ";
        cout<<r[tot]<<" ";
        tot=r[tot];

    }

代码

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
const int N=2e6+5;
int a[N];
//int l[N],r[N];//左指针数组，右指针数组
map<int,int> l,r;
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l[a[i]]=a[i-1];
        r[a[i-1]]=a[i];
    }
    r[a[n]]=-1145;
    int T;
    cin>>T;
    while(T--){
        int op,x,y;
        cin>>op;
        if(op==1){
            cin>>x>>y;
            l[r[x]]=y;
            l[y]=x;
            int d=r[x];
            r[l[y]]=y;
            r[y]=d;
        }
        else{
            cin>>x;
            int L=l[x];
            int R=r[x];

            l[R]=l[x];
            r[L]=r[x];

        }
    }
    int tot=0;
    while(r[tot]!=-1145){
        //cout<<tot<<" ";
        cout<<r[tot]<<" ";
        tot=r[tot];

    }

}

这道题是一道练习链表很好的题目。