連結リストに似たアルゴリズムを用います。

具体的には、現在の \(A\) の中に現れるそれぞれの値 \(i\) について、\(A\) の中で \(i\) の直後に現れる値（\(i\) が末尾にあるならば \(-1\)）を \(\text{next}_i\) と定義し、これを管理することを考えます。

はじめ、\(A\) の中に現れる値は \(0\) のみであり、\(\text{next}_0=-1\) です。

\(1\) 種類目のクエリ、すなわち値 \(x\) の直後に値 \(i\) を挿入する操作について考えます。\(i\) を挿入する前の \(\text{next}_x\) の値を \(y\) とおくと、元々 \(\dots\rightarrow x\rightarrow y\rightarrow \dots\) となっていた所が \(\dots\rightarrow x\rightarrow i\rightarrow y\rightarrow \dots\) というように変化するわけですから、\(\text{next}_x\) の値が \(i\) に、\(\text{next}_i\) の値が \(y\) にそれぞれ更新され、逆にそれ以外の更新はありません。

\(2\) 種類目のクエリ、すなわち値 \(x\) と値 \(y\) の間にある値の合計を出力し、それらを削除するという操作について考えます。

まず、\(A\) の中で \(x\) が \(y\) よりも先に現れると分かっている場合について考えます。この場合、\(x\) から始めて \(x\rightarrow \text{next}_x \rightarrow \text{next}_{\text{next}_x} \rightarrow \dots\) というように辿っていき、\(y\) に到達するまで続ければ、\(x\) と \(y\) の間にある要素が全てわかります。その後これらの要素を削除するためには、単に \(\text{next}_x\) の値を \(y\) に更新すればよいです。削除される要素の数に比例する計算量がかかりますが、要素の追加が高々 \(Q\) 回しか起こらないことから、削除される要素の数も合計で高々 \(Q\) 個に抑えられます。

\(A\) の中で \(y\) が \(x\) よりも先に現れると分かっている場合も、同様に \(y\) から始めて \(y\rightarrow \text{next}_y \rightarrow \text{next}_{\text{next}_y} \rightarrow \dots\) と辿っていけばよいです。

問題は、実際には \(A\) の中で \(x\) と \(y\) のどちらが先に現れるのか分からないことです。しかし、\(x\rightarrow \text{next}_x \rightarrow \text{next}_{\text{next}_x} \rightarrow \dots\) と辿っていく過程と \(y\rightarrow \text{next}_y \rightarrow \text{next}_{\text{next}_y} \rightarrow \dots\) と辿っていく過程を \(1\) ステップずつ交互に進めていき、前者が \(y\) に到達した or 後者が \(x\) に到達したタイミングで打ち切れば、削除される要素数の \(2\) 倍程度のステップ数で済むことになり、全体の計算量を変わらず \(O(Q)\) に抑えることができます。

実装例 (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;
                    }
                }
            }
        }
    }
}