We can use an algorithm similar to linked list.

Specifically, for each value \(i\) in the current \(A\), we manage the value \(\text{next}_i\) representing the value occurring right after \(i\) in \(A\). (If \(i\) is at the end, define the value as \(-1\).)

Initially, \(0\) is the only value contained in \(A\), and \(\text{next}_0=-1\).

Consider a query of the first kind: you are asked to insert \(i\) right after the value \(x\). If \(\text{next}_x\) before the insertion was \(y\), the chain \(\dots\rightarrow x\rightarrow y\rightarrow \dots\) becomes \(\dots\rightarrow x\rightarrow i\rightarrow y\rightarrow \dots\), so \(\text{next}_x\) should be updated to \(i\), and \(\text{next}_i\), and no other values need to be updated.

Consider a query of the second kind: print the sum of the values between \(x\) and \(y\) and remove them.

First, if \(x\) is known to occur earlier than \(y\), we may start from \(x\) and traverse as \(x\rightarrow \text{next}_x \rightarrow \text{next}_{\text{next}_x} \rightarrow \dots\) until reaching \(y\); this procedure gives us all the elements between \(x\) and \(y\). To remove them, simply set \(\text{next}_x\) to \(y\). Although this procedure require the time proportional to the number of deleted elements, since an insertion occurs at most \(Q\) times, the total number of deleted elements is also bounded by \(Q\).

If \(y\) is known to occur earlier than \(x\), we can likewise start from \(y\) and traverse as \(y\rightarrow \text{next}_y \rightarrow \text{next}_{\text{next}_y} \rightarrow \dots\).

The problem is we do not know which of \(x\) and \(y\) occurs earlier in \(A\). Nevertheless, we can advance the steps \(x\rightarrow \text{next}_x \rightarrow \text{next}_{\text{next}_x} \rightarrow \dots\) and \(y\rightarrow \text{next}_y \rightarrow \text{next}_{\text{next}_y} \rightarrow \dots\) alternately, and stop the process once either traversal reaches \(y\). This procedure requires the number of steps twice as many as the number of deleted elements, and the computational complexity is still bounded by \(O(Q)\) time.

Sample code (C++):

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<int> next(q + 1);
    next[0] = -1;
    for (int i = 1; i <= q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            next[i] = next[x];
            next[x] = i;
        } else {
            int x, y;
            cin >> x >> y;
            int cx = x, cy = y;
            long long sx = 0, sy = 0;
            while (true) {
                if (next[cx] != -1) {
                    cx = next[cx];
                    if (cx == y) {
                        cout << sx << '\n';
                        next[x] = y;
                        break;
                    } else {
                        sx += cx;
                    }
                }
                if (next[cy] != -1) {
                    cy = next[cy];
                    if (cy == x) {
                        cout << sy << '\n';
                        next[y] = x;
                        break;
                    } else {
                        sy += cy;
                    }
                }
            }
        }
    }
}