题解：P1196 [NOI2002] 银河英雄传说

Karmallis · 2026-01-20 19:07:57 · 题解

看到题解区这么多人写带权并查集，Treap，LCT 这些高级的数据结构我感到很汗。

其实我们完全不需要那些高级的数据结构，只需要维护一堆链表，合并的时候让小的链表插到大的链表上，并且记录战舰之间的相对位置，按题意模拟即可。

参考启发式合并堆，由于启发式合并时链表大小必定加倍所以时间复杂度是 O(n\log{}n) 的。

AC Code：

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

constexpr int N=5e5+9;
int m,x[N],y[N]; //x: in which queue; y: on which position
list<int> q[N];

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    for(int i=1;i<N;i++) q[i].push_back(x[i]=i);
    cin>>m;
    while(m--){
        char opt;
        int l,r;
        cin>>opt>>l>>r;
        if(opt=='M'){
            auto &l_q=q[x[l]],&r_q=q[x[r]];
            if(l_q.size()<r_q.size()){ //push all of queue of l to bottom of r
                for(;l_q.size();l_q.pop_front()){
                    x[l_q.front()]=x[r];
                    y[l_q.front()]=y[r_q.back()]+1;
                    r_q.push_back(l_q.front());
                }
            }
            else{
                for(;r_q.size();r_q.pop_back()){ //push all of queue of r to front of l
                    x[r_q.back()]=x[l];
                    y[r_q.back()]=y[l_q.front()]-1;
                    l_q.push_front(r_q.back());
                }
            }
        }
        else{
            if(x[l]!=x[r]) cout<<"-1\n";
            else cout<<abs(y[r]-y[l])-1<<'\n';
        }
    }
    return 0;
}