[AT_abc344_e Insert or Erase]

FallingFYC_ · 2024-03-09 22:42:27 · 题解

原题

e 比 d 简单（这是我的首场 AT）。

思路

看到对一个数组进行插入和删除两种操作，一眼双向链表。题目中并未给定元素的下标，只给了元素，需要开一个 stl::map 记录一下。

然后就没了（太水了吧）。

代码

我手写的链表。

#include "bits/stdc++.h"
using namespace std;
struct node
{
    int num , lst , nxt;
}l[400005];
int n , a , cnt , q , op , x , y , fir;
map<int , int > pos;
int main()
{
    cin >> n;
    for (int i = 1 ; i <= n ; i++)
    {
        cin >> a;
        l[i] = {a , i - 1 , i + 1};
        pos[a] = i;
        if (i == 1) l[i].lst = -1;
        if (i == n) l[i].nxt = -1;
    }
    cnt = n; fir = 1;
    cin >> q;
    while (q--)
    {
        cin >> op >> x;
        if (op == 1)
        {
            cin >> y;
            pos[y] = ++cnt;
            l[cnt] = {y , pos[x] , l[pos[x]].nxt};
            if (l[pos[x]].nxt != -1) l[l[pos[x]].nxt].lst = pos[y];
            l[pos[x]].nxt = pos[y];
        }
        else
        {
            if (pos[x] == fir) fir = l[pos[x]].nxt;
            if (l[pos[x]].lst != -1) l[l[pos[x]].lst].nxt = l[pos[x]].nxt;
            if (l[pos[x]].nxt != -1) l[l[pos[x]].nxt].lst = l[pos[x]].lst;
            l[pos[x]] = {0 , -1 , -1};
            pos[x] = 0;
        }
    }
    node now = l[fir];
    while (1)
    {
        cout <<now.num << ' ';
        if (now.nxt == -1) break;
        now = l[now.nxt];
    }
    return 0;
}