P1503 鬼子进村

    • 254通过
    • 543提交
  • 题目提供者 cyrcyr
  • 评测方式 云端评测
  • 标签 平衡树 树形结构
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》,剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队,于是独立团与鬼子展开游击战。

    题目描述

    描述 县城里有n个用地道相连的房子,第i个只与第i-1和第i+1个相连。这是有m个消息依次传来

    1、消息为D x:鬼子将x号房子摧毁了,地道被堵上。

    2、消息为R :村民们将鬼子上一个摧毁的房子修复了。

    3、消息为Q x:有一名士兵被围堵在x号房子中。

    李云龙收到信息很紧张,他想知道每一个被围堵的士兵能够到达的房子有几个。

    输入输出格式

    输入格式:

    第一行2个整数n,m(n,m<=50000)。

    接下来m行,有如题目所说的三种信息共m条。

    输出格式:

    对于每一个被围堵的士兵,输出该士兵能够到达的房子数。

    输入输出样例

    输入样例#1: 复制
    7 9
    D 3
    D 6
    D 5
    Q 4
    Q 5
    R
    Q 4
    R
    Q 4
    
    输出样例#1: 复制
    1
    0
    2
    4
    

    说明

    若士兵被围堵在摧毁了的房子中,那只能等死了。。。。。。

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