星际争霸

Grade 100 Open Time Thursday, 18 June 2020, 11:10 AM
Discount 0.8 Time Discount Thursday, 18 June 2020, 11:10 AM
Allow late Yes Close Time Thursday, 18 June 2020, 11:10 AM
Input file galaxy.in Output file galaxy.out

【题目描述】星际争霸(galaxy) NOI 2002

第一次大规模星际演习正式开始,由红方琳琳,蓝方小光各率领十万余艘太空战舰模拟对抗。

小光将星域战场划分成30 000列,每列依次编号为1,2,…,30 000。之后,他把自己的战舰也依次编号为1,2,…,30 000,让第i号战舰处于第i列(i=1,2,…,30 000),形成“一字长蛇阵”,诱敌深入。这是初始阵形。当进犯之敌到达时,小光会多次发布合并指令,将大部分战舰集中在某几列上,实施密集攻击。合并指令为M i j,含义为让第i号战舰所在的整个战舰队列,作为一个整体(头在前尾在后)接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

但琳琳早已在战略上取得了主动。在交战中,她可以通过庞大的情报网络随时监听小光的舰队调动指令。

在小光发布指令调动舰队的同时,琳琳为了及时了解当前小光的战舰分布情况,也会发出一些询问指令:C i j。该指令意思是,询问电脑,小光的第i号战舰与第j号战舰当前是否在同一列中,如果在同一列中,那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员,你被要求编写程序分析小光的指令,以及回答琳琳的询问。

【输入格式】   

第1行有1个整数T(1≤T≤500 000),表示总共有T条指令。

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

(1) M i j :i和j是两个整数(1≤i,j≤30 000),表示指令涉及的战舰编号。该指令是琳琳监听到的小光发布的舰队调动指令,并且保证第i号战舰与第j号战舰不在同一列。

(2) C i j :i和j是两个整数(1≤i,j≤30 000),表示指令涉及的战舰编号。该指令是琳琳发布的询问指令。

【输出格式】  

你的程序应当依次对输入的每一条指令进行分析和处理:

如果是小光发布的舰队调动指令,则表示舰队排列发生了变化,你的程序要注意到这一点,但是不要输出任何信息;

如果是琳琳发布的询问指令,你的程序要输出一行,仅包含一个整数,表示在同一列上,第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上,则输出-1。

【输入样例】

4

M 2 3

C 1 2

M 2 4

C 4 2

【输出样例】 

-1

1