Why can this problem be solved using a linked list? Because this problem only requires outputting the entire sequence at the end, rather than performing real - time queries. The problem guarantees that the elements in \(A\) are distinct, which is the core reason why a linked list can be used.

The block - dividing algorithm has broader applicability and its code is clear and straightforward.

Consider dividing the sequence into \(\sqrt{n}\) blocks, and each block is dynamically maintained using a vector, that is, all the numbers in this block are placed in the corresponding vector. When inserting a number after a certain element, we only need to insert it into the vector of the corresponding block of this element. Since the size of the vector of each block is only \(\sqrt{n}\), the time complexity of insertion is only \(O(\sqrt{n})\). The same principle applies when deleting a number.

However, can we really ensure that the size of each vector is always \(\sqrt{n}\)? If we add a large number of numbers at a fixed position, the size of the corresponding vector may reach the order of \(O(n)\). Therefore, we consider block reconstruction. That is, re - group the entire sequence so that the sizes of all vectors become more evenly distributed.

When can we perform block reconstruction? Block reconstruction takes \(O(n)\) time. Obviously, we can’t reconstruct every time we add a number. We can reconstruct once every \(\sqrt{n}\) operations. The complexity of block reconstruction is \(O(n\sqrt{n})\).

The overall time complexity is also \(O(n\sqrt{n})\). In fact, the insert operation of vector is very fast, so it is not much slower than the linked - list algorithm.

Precautions:

• The problem is not about adding a number after a certain position, but adding a number after a certain element. Therefore, we need to create an array \(bel_x\) representing which block \(x\) is in the sequence.

• In this problem, the value range is large. If we use the \(bel\) array, discretization is required. If we use map, the complexity will become \(O(n\sqrt{n}\log n)\), which will lead to a Time Limit Exceeded (TLE)!

my code:

// 394ms
#include <bits/stdc++.h>
using namespace std;

const int N = 6e5 + 5, M = 2000;

int n, q, a[N], lx[N], rx[N], len, b[N], tot;
int tmp[N], tl, sum[M], bel[N];
vector<int> bk[M];
// vector<int> bk[i] stores the numbers within this block
// lx[i] and rx[i] store the left and right endpoints of this block respectively
// bel[i] stores the block where this number is located

struct edge {
  int op, l, r;
}ed[N]; 

signed main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[++tot] = a[i];
  int sq = sqrt(n);
  len = n / sq;
  for (int i = 1; i <= n / sq; i++) lx[i] = (i - 1) * sq + 1, rx[i] = lx[i] + sq - 1;
  if (n % sq) {
    len++;
    lx[len] = rx[len - 1] + 1;
    rx[len] = n;
  }
  int cnt = 0;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d", &ed[i].op);
    if (ed[i].op == 1) scanf("%d%d", &ed[i].l, &ed[i].r), b[++tot] = ed[i].l, b[++tot] = ed[i].r;
    else scanf("%d", &ed[i].l); 
  }
  sort(b + 1, b + tot + 1);
  tot = unique(b + 1, b + tot + 1) - b - 1;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
  for (int i = 1; i <= q; i++) {
    if (ed[i].op == 1) ed[i].r = lower_bound(b + 1, b + tot + 1, ed[i].r) - b;
    ed[i].l = lower_bound(b + 1, b + tot + 1, ed[i].l) - b; 
  }
  for (int i = 1; i <= len; i++) {
    for (int j = lx[i]; j <= rx[i]; j++) bk[i].push_back(a[j]), bel[a[j]] = i; 
  }
  for (int cas = 1; cas <= q; cas++) {
    int op = 0, l = 0, r = 0;
    op = ed[cas].op;
    cnt++;
    if (op == 1) {
      l = ed[cas].l, r = ed[cas].r;
      int L = bel[l], lenb = bk[L].size(); // L is the block where l is located. 
      for (int i = 0; i < lenb; i++) {
        if (bk[L][i] == l) {
          l = i;
          break;
        }
      }
      if (l == lenb - 1) bk[L].push_back(r);
      else bk[L].insert(bk[L].begin() + l + 1, r);  
      bel[r] = L;
      rx[L]++;
      for (int i = L + 1; i <= len; i++) lx[i]++, rx[i]++;
    }
    if (op == 2) {
      l = ed[cas].l;
      int L = bel[l], lenb = bk[L].size();
      for (int i = 0; i < lenb; i++) {
        if (bk[L][i] == l) {
          l = i;
          break;
        }
      }
      bel[bk[L][l]] = 0;
      bk[L].erase(bk[L].begin() + l);
      rx[L]--;
      for (int i = L + 1; i <= len; i++) lx[i]--, rx[i]--;
    }
    if (cnt >= 5 * sq) { // Block reconstruction after a certain number of times
      tl = 0;
      for (int i = 1; i <= len; i++) {
        for (auto j : bk[i]) tmp[++tl] = j;
      }
      sq = sqrt(tl);
      len = tl / sq;
      for (int i = 1; i <= tl / sq; i++) {
        lx[i] = (i - 1) * sq + 1, rx[i] = lx[i] + sq - 1; 
      }
      if (tl % sq) {
        len++;
        lx[len] = rx[len - 1] + 1;
        rx[len] = tl;
      }
      for (int i = 1; i <= len; i++) {
        bk[i].clear();
        for (int j = lx[i]; j <= rx[i]; j++) bk[i].push_back(tmp[j]), bel[tmp[j]] = i; 
      }
      cnt = 0;
    }
  }
  for (int i = 1; i <= len; i++) {
    if (bk[i].size() == 0) continue;  
    for (auto v : bk[i]) printf("%d ", b[v]);
  }
}