rt，场上想到了链表做法，但是TLE了6个点，求优化，最坏复杂度确实可以到 $O(Q^2)$ ，如果我的做法是假的，您可以告诉我一下正解

#include <bits/stdc++.h>
using namespace std;
const int N=500010;
int l[N],r[N];
int main(){
    int Q;
    cin>>Q;
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    l[0]=-1;
    r[0]=-1;
    for(int i=1;i<=Q;i++){
        int type;
        cin>>type;
        if(type==1){
            int x;
            cin>>x;
            int next=r[x];
            r[x]=i;
            l[i]=x;
            r[i]=next;
            if(next!=-1){
                l[next]=i;
            }
        }
        else{
            int x,y;
            cin>>x>>y;
            bool flag=false;
            int cur=r[x];
            while(cur!=-1){
                if(cur==y){
                    flag=true;
                    break;
                }
                cur=r[cur];
            }
            long long sum=0;
            if(flag){
                cur=r[x];
                while(cur!=y){
                    sum+=cur;
                    int next=r[cur];
                    r[l[cur]]=r[cur];
                    if(r[cur]!=-1){
                        l[r[cur]]=l[cur];
                    }
                    cur=next;
                }
                r[x]=y;
                l[y]=x;
            }
            else{
                cur=r[y];
                while(cur!=x){
                    sum+=cur;
                    int next=r[cur];
                    r[l[cur]]=r[cur];
                    if(r[cur]!=-1){
                        l[r[cur]]=l[cur];
                    }
                    cur=next;
                }
                r[y]=x;
                l[x]=y;
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}