1. 题目

传送门

题目很长，大意如下：

你有 30000 条队列, 最开始每条队列头部有一个元素, 元素编号 1~n。有 k 条指令,1. 合并
指令,M i j, 将 i 号元素所在队列整体 (队列内相对位置不改变) 移动到 j 号元素所在队列
尾部;2. C i j, 查询 i j 是否在一个队列中, 如果在, 输出他们隔了多少个元素。

2. 题解

这是在并查集题集里的一题
然而。。。去他娘的并查集，劳资打的就是启发式！c++，把你他娘的双端队列端上来！
所以我们要抛弃并查集，用启发式合并。
这样思考难度大大降低
首先如果数据很小，那么我们直接模拟就行了，搞 30K 个队列，然后一个一个把元素从某个队列取出放到另一个队列队尾。
然而不难发现这会超时。
但是。。。我们可以用启发式合并呀！
把队列 a 放到队列 b 后面不久等于把队列 b 放队列 a 前面吗？
因此，我们搞双端队列 (deque)，当命令为 M a b（把 a 接到 b 后面）的时候看，如果 a 的 size 较大，就把 b 放 a 前面，否则把 a 放 b 后面，每次记录每个元素所在的队列编号和队列中的位置。
因为插入到前面的时候，被插入的队列的首端元素的位置为 0，我们不可能把那整个队列后面的元素位置都加 1，所以我们直接让新插入的元素的编号为插入后它后面的元素的编号减一即可（也就是说可能有负数）。

这样总复杂度是 nlogn 的 (n=30K).

代码：

#include <bits/stdc++.h>
#define NS (30005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
int t,h[NS],pos[NS];
char opt[10];
deque<int> q[NS];
int main()
{
    IN(t);
    for(int i=1;i<NS;i++)h[i]=i,q[i].push_back(i);
    for(int i=1,a,b;i<=t;i++)
    {
        scanf("%s",opt),IN(a),IN(b);
        if(opt[0]=='M')
        {
            int h1=h[a],h2=h[b];
            if(q[h1].size()>q[h2].size())
            {
                for(int j=q[h2].size()-1;j>=0;j--)
                {
                    q[h1].push_front(q[h2][j]);
                    h[q[h1][0]]=h1,pos[q[h1][0]]=pos[q[h1][1]]-1;
                }
                q[h2].clear();
            }
            else
            {
                for(int j=0;j<q[h1].size();j++)
                {
                    h[q[h1][j]]=h2,pos[q[h1][j]]=pos[q[h2][q[h2].size()-1]]+1;
                    q[h2].push_back(q[h1][j]);
                }
                q[h1].clear();
            }
        }
        else
        {
            if(h[a]!=h[b]){puts("-1");continue;}
            if(pos[a]<pos[b])swap(a,b);
            printf("%d\n",pos[a]-pos[b]-1);
        }
    }
    return 0;
}