题解 [ABC344E] Insert or Erase

odt63 · 2024-03-10 08:57:30 · 题解

Solution:

本题需要模拟一个链表，考虑需要加入时需要知道一个点的后继，删除时需要知道一个点的前驱和后继，所以我们采用双向链表维护。用数组维护每个点的前驱和后继。由于值域是 10^9 的，所以我们采用map维护。

首先考虑构建链表。我们把序列中的点顺次放入链表中，具体地说，对于每个点 a_i，它的前驱是 a_{i-1}，后继是 a_{i+1}。特别地，我们建立两个虚拟节点，分别作为 a_1 的前驱和 a_n 的后继。

考虑添加点。我们很容易得知要添加点的左右两个点 L 和 R，设添加的点为 X，对于后继，把 L 的后继连向 X，X 的后继连向 R，前驱同理，如图所示：

考虑删除。我们很容易得知要删除点的左右两个点 L 和 R，把 L 的后继连向 R，R 的前驱连向 L 如图所示：

最后从最左边的虚拟点开始，向右寻找后继输出，直至寻找到最右边的点，输出结束。

时间复杂度 O(n \log n)。

Code:

// By 0x0F
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int pL = -1, pR = 1145141919810LL;
unordered_map<int ,int> nxt, frm;
int a[200010];
signed main() {
    int n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    a[0] = pL, a[n + 1] = pR;
    nxt[pL] = a[1], nxt[a[n]] = pR, frm[pR] = a[n], frm[a[1]] = pL;
    for (int i = 1; i < n; i++) nxt[a[i]] = a[i + 1];
    for (int i = 2; i <= n; i++) frm[a[i]] = a[i - 1];
    int q = read();
    while (q--) {
        int op = read();
        if (op == 1) {
            int x = read(), y = read();
            int xl = x, xr = nxt[x];
            nxt[xl] = y, nxt[y] = xr;
            frm[xr] = y, frm[y] = xl;
        } else {
            int x = read();
            int xl = frm[x], xr = nxt[x];
            nxt[xl] = xr, frm[xr] = xl;
        }
        int st = nxt[pL];
    }
    int st = nxt[pL];
    while (st != pR) {
        printf("%lld ", st);
        st = nxt[st];
    } 
    return 0;
}