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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *