P2342 叠积木

    • 303通过
    • 897提交
  • 题目提供者 wwqk4444
  • 评测方式 云端评测
  • 标签 并查集 USACO
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    Cube Stacking, 2004 Open

    题目描述

    约翰和贝西在叠积木。共有30000块积木,编号为1到30000。一开始,这些积木放在地上,自然地分成N堆。贝西接受约翰的指示,把一些积木叠在另一些积木的上面。一旦两块积木相叠, 彼此就再也不会分开了,所以最后叠在一起的积木会越来越高。约翰让贝西依次执行P条操作,操作分为两种:

     第一种是移动操作,格式为“移动X到Y的上面”。X和Y代表两块积木的编号,意思是将X所的那堆积木,整体叠放到Y所在的那堆积木之上;

     第二种是统计操作,格式为“统计Z下方的积木数量”。Z代表一块积木的编号,意思是贝西需要报告在编号为Z的积木之下还有多少块积木

    请编写一个程序,帮助贝西回答每条统计问题。

    输入输出格式

    输入格式:

     第一行:单个整数:P,1 ≤ P ≤ 10^5

     第二行到第P + 1行:每行描述一条命令,如果这行开头的字母是 M,代表一条移动命令,后面的两个整数代表上文中的X和Y;如果开头字母是 C,代表一条统计命令。后面的整数代表上文中的Z,保证所有的移动命令都有意义,X和Y不会已经出现在同一堆积木里

    输出格式:

     对每一个统计命令,输出正确回答,用换行符分开每个查询的结果

    输入输出样例

    输入样例#1: 复制
    6
    M 1 6
    C 1
    M 2 4
    M 2 6
    C 3
    C 4
    输出样例#1: 复制
    1
    0
    2

    说明

    第一次查询时, 1 下面只有一个 6;第二次查询时, 3 下面没有任何积木;第三次查询时,4 下面有两块积木:1 和 6

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。