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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 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;
}