TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2281
  • 题目
  • P2281方块游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    FJ 和贝茜 用 N (1 <= N <= 30,000)块相同的小立方块玩游戏,小方块编号为 1..N。开始时,小方块都单独分开的, 每个看成一个柱子, 即有 N 柱子。 FJ 要 贝茜做 P(1 <= P <= 100,000) 个操作,操作有两种类型:
    (1) FJ 要求贝茜把X 号方块所在的柱子放到 Y号所在的柱子上面,成一个新柱子。
    (2)FJ 要求贝茜计算 X 号方块所在柱子,它下面有多少个小方块。
    请编个程序,帮助贝茜计算。

    输入格式

    *第一行:一个整数 P
    *第 2..P+1行:第 i+1行表示第 i个FJ要求的合法操作。如果这行以'M'开头,后面有两个整数 X,y 表示要进入(1)操作。
    如果这行以'C'开头,后面有一个整数 X,表示要求计算 X所在柱子下面的方块个数。

    注:所有操作都是合法的。N 并没有出现在输入文件中。

    输出格式

    依次要求计算的值,每次一行。

    样例输入 1

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

    样例输出 1




    样例输入 2

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

    样例输出 2

    1
    0
    1
    0
    2
    2
    1
    3
    0

    提示

    样例说明:
    6 : 6 个操作
    M 1 6 : 1,6 / 2 / 3 / 4 / 5 把 1放在 6 上面。
    C 1 : 输出:1
    M 2 4 : 1,6 / 2,4 / 3 / 5
    M 2 6 : 2,4,1,6 / 3 / 5
    C 3 : 输出 :0
    C 4 : 输出: 2


    来源  USACO OPEN 2004 cubes