大自然历七九九年,宇宙历七玖玖年

输入输出样例

输入样例#1:

4
M 2 3
C 1 2
M 2 4
C 4 2

出口样例#1:

-1
1

输入文件galaxy.in的首先行有二个整数T(1<=T<=500,000),表示总共有T

输入输出格式

输入格式:

 

输入文件galaxy.in的第三行有三个整数T(壹<=T<=500,000),表示总共有T

条指令。

以下有T行,每行有一条指令。指令有二种格式:

  1. M i j :i和j是多个整数(1<=i ,
    j<=三千0),表示指令涉及的军舰编号。

该指令是莱因哈特窃听到的杨威利发布的舰队调动指令,并且保障第i号战

舰与第j号战舰不在同壹列。

  1. C i j :i和j是多少个整数(一<=i ,
    j<=20000),表示指令涉及的舰艇编号。

该指令是莱因哈特宣布的打听指令。

 

出口格式:

 

出口文件为galaxy.out。你的程序应该依次对输入的每一条指令展开解析和

处理:

假如若杨威利公布的舰队调动指令,则象征舰队排列发生了变通,你的次第

要注意到那点,可是并非输出任何音信;

借使是莱因哈特发布的刺探指令,你的程序要出口一行,仅包涵1个整数,

意味着在一如既往列上,第i 号战舰与第j 号战舰之间布署的舰只数目。要是第i 号战

舰与第j号战舰当前不在同壹列上,则输出-1。

 

处理:

P11九陆 银河铁汉旧事

要是是杨威利发布的舰队调动指令,则代表舰队排列产生了变动,你的先后

说明

【样例表明】

战舰地方图:表格中阿拉伯数字代表战舰编号

图片 1

加权并查集。记录下每艘船与最前边的船的距离。并且并查集判断是还是不是在同一列上。

 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 const int MAXN = 30100;
 7 struct node{
 8     int fa,pos,num;    //祖先,与队首的距离,这一队中船的数量 
 9 }s[MAXN];
10 char ch[5];
11 int t,n;
12 
13 int find(int x)
14 {
15     if(x!=s[x].fa)
16     {
17         int p = s[x].fa;
18         s[x].fa = find(s[x].fa);
19         s[x].pos = s[x].pos+s[p].pos-1;    //更新船的位置 
20     }
21     return s[x].fa;
22 }
23 void Change(int x,int y)
24 {
25     int rx = find(x);
26     int ry = find(y);
27     s[rx].fa = ry;
28     s[rx].pos = s[ry].num+1;    
29     s[ry].num += s[rx].num;    //合并后船的数量 
30     s[rx].num = 0;    //没船后,变为0 
31 }
32 void Query(int x,int y)
33 {
34     int rx = find(x);
35     int ry = find(y);
36     if (rx!=ry) printf("-1\n");    //并查集判断是否在同一队 
37     else printf("%d\n",abs(s[x].pos-s[y].pos)-1);
38 }
39 int main()
40 {
41     scanf("%d",&t);
42     for (int i=1; i<=30000; ++i)
43     {
44         s[i].fa = i;
45         s[i].num = 1;
46         s[i].pos = 1;
47     }
48     for (int i=1; i<=t; ++i)
49     {
50         int x,y;
51         scanf("%s%d%d",ch,&x,&y);
52         if (ch[0]=='M') Change(x,y);
53         else Query(x,y);
54     }
55     return 0;
56 }

侵略之敌到达时,杨威利会多次透露合并指令,将多数战舰集中在某几列上,

难点叙述

公元伍8○一年,地球居民动员搬迁至金牛座α第3行星,在那里发布银河联邦

创设宣言,同年改元为宇宙历元年,并起先向银系深处进行。

宇宙历柒九九年,银系的两大军事企业在巴米利恩星域产生战争。天柱山压

顶集团派宇宙舰队司令莱因哈特引导八万余艘舰船出征,气吞山河公司点主力杨

威利集团下级两万艘战舰迎敌。

杨威利擅长排兵布阵,巧妙运用各样战术屡次以少胜多,难免恣生骄气。在

此番决战中,他将巴米利恩星域战场划分成两千0列,每列依次编号为一, 贰, …,

贰仟0。之后,他把温馨的军舰也相继编号为一, 二, …, 30000,让第i号战舰处于

第i列(i = 1, 二, …, 30000),形成“一字金锁阵”,诱敌深刻。这是开头阵形。当

侵犯之敌到达时,杨威利会数十四遍宣告合并指令,将多数军舰集中在某几列上,

举行密集攻击。合并指令为M i j,含义为让第i号战舰所在的整整战舰队列,作

为一个完完全全(头在前尾在后)接至第j号战舰所在的舰只队列的尾巴部分。显著战舰

队列是由远在同1列的3个或多个战舰构成的。合并指令的执行结果会使队列增

大。 然则,大巧若拙的莱因哈特早已在战略上取得了积极性。在交火中,他得以通

过巨大的情报互连网随时监听杨Willie的舰队调动指令。

在杨威利发表指令调动舰队的还要,莱因哈特为了及时了然当前杨威利的战

舰分布情形,也会时有发生一些打听指令:C i j。该指令意思是,询问电脑,杨威利

的第i号战舰与第j号战舰当前是否在平等列中,借使在壹如既往列中,那么它们之

间安插有微微战舰。

作为八个有名的高等程序设计员,你被须求编写程序分析杨威利的指令,以

及应对莱因Hart的问询。

末尾的决战已经进展,银河的野史又迈出了1页……

【样例表明】

图片 2

实施密集攻击。合并指令为M i j,含义为让第i号战舰所在的万事战舰队列,作

及应对莱因哈特的刺探。

假如若莱因哈特发布的问询指令,你的先后要出口1行,仅包含3个平头,

公元伍八○一年,地球居民搬迁至狮子座α第3行星,在那边公布银河联邦

末段的决战已经进展,银河的野史又迈出了1页……

此次决战中,他将巴米利恩星域战场划分成三千0列,每列依次编号为一, 二, …,

该指令是莱因哈特窃听到的杨Willie公布的舰队调动指令,并且保险第i号战

 

意味着在相同列上,第i 号战舰与第j 号战舰之间计划的舰只数目。倘使第i 号战

创建宣言,同年改元为宇宙历元年,并开首向银系深处进行。

以下有T行,每行有一条指令。指令有二种格式:

杨威利擅长排兵布阵,巧妙利用各个战术屡次以少胜多,难免恣生骄气。在

间陈设有多少战舰。

大。 但是,深谋远虑的莱因哈特早已在战略上获取了积极。在交火中,他得以通

要留心到这点,可是绝不输出任何音信;

  1. M i j :i和j是多个整数(一<=i ,
    j<=三千0),表示指令涉及的舰船编号。

为3个整机(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。鲜明战舰

过巨大的情报互连网随时监听杨威利的舰队调动指令。

顶公司派宇宙舰队司令莱因哈特带领七千0余艘舰艇出征,气吞山河集团点老将杨

先看数量大小,和M的操作,就知晓使用并查集,大家用一个front数组记录那个数从前有4个人,然后用num数组记录这列有多少个数字,由于是几度查询,于是就选拔了前缀和求出答案即可~

舰与第j号战舰当前不在同1列上,则输出-一。

-1
1

宇宙历柒玖九年,银系的两大军事集团在巴米利恩星域发生战争。敬亭山压

舰与第j号战舰不在同1列。

出口文件为galaxy.out。你的先后应该依次对输入的每一条指令展开辨析和

两千0。之后,他把温馨的军舰也逐条编号为壹, 二, …, 三千0,让第i号战舰处于

在杨威利公布命令调动舰队的同时,莱因哈特为了及时精通当下杨威利的战

舰分布情况,也会时有发生壹些明白指令:C i j。该指令意思是,询问电脑,杨威利

输入格式:

战舰地点图:表格中阿拉伯数字代表战舰编号

输出样例#1:

用作多个有名的高等级程序设计员,你被要求编写程序分析杨威利的通令,以

第i列(i = 一, 2, …, 三千0),形成“一字出水阵”,诱敌深切。那是初步阵形。当

的第i号战舰与第j号战舰当前是还是不是在同样列中,就算在同1列中,那么它们之

威利公司下级两千0艘舰艇迎敌。

该指令是莱因哈特发布的摸底指令。

  1. C i j :i和j是多少个整数(壹<=i ,
    j<=20000),表示指令涉及的舰只编号。

条指令。

输入样例#1:

输出格式:

4
M 2 3
C 1 2
M 2 4
C 4 2
#include<bits/stdc++.h>
#define maxn 300000
using namespace std;
int n;
int pre[maxn],front[maxn],num[maxn];

int find(int x) {if(x==pre[x])return x;int f=find(pre[x]);front[x]+=front[pre[x]];return pre[x]=f;}

void init()
{
    for(int i=1;i<=n;i++)
    {
        pre[i]=i;
        front[i]=0;
        num[i]=1;
    }
}

int main()
{
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
    {
        char c;
        int t1,t2;
        cin>>c>>t1>>t2;
        int fx=find(t1),fy=find(t2);
        if(c=='M')      
        {
            front[fx]+=num[fy];
            pre[fx]=fy;
            num[fy]+=num[fx];
            num[fx]=0;
        }
        if(c=='C')  
        {
            if(fx!=fy) cout<<"-1\n";
            else cout<<abs(front[t1]-front[t2])-1<<endl;
        }
    }
    return 0;
} 

队列是由远在同壹列的二个或几个战舰构成的。合并指令的举行结果会使队列增

相关文章