P3797 妖梦斩木棒

    • 123通过
    • 496提交
  • 题目提供者 orangebird
  • 评测方式 云端评测
  • 标签 概率论,统计 模拟 线段树 洛谷原创
  • 难度 提高+/省选-
  • 时空限制 2000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    妖梦是住在白玉楼的半人半灵,拥有使用剑术程度的能力。

    题目描述

    有一天,妖梦正在练习剑术。地面上摆放了一支非常长的木棒,妖梦把它们切成了等长的n段。现在这个木棒可以看做由三种小段构成,中间的n-2段都是左右都被切断的断头,我们记做’X’,最左边的一段和最右边的一段各有一个圆头,记做’(‘和’)’。幽幽子吃饱后闲来无事,决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒,来替换掉妖梦切下来的n段中的一部分,然后问妖梦一些问题。这些操作可以这样描述:

    1 x C 将第x个小段的木棒替换成C型,C只会是’X’,’(‘,’)’中的一种

    2 l r 询问妖梦从第l段到第r段之间(含l,r),有多少个完整的木棒

    完整的木棒左右两端必须分别为’(‘和’)’,并且中间要么什么都没有,要么只能有’X’。

    虽然妖梦能够数清楚这些问题,但幽幽子觉得她回答得太慢了,你能教给妖梦一个更快的办法吗?

    输入输出格式

    输入格式:

    第一行两个整数n,m,n表示共有n段木棒,m表示有m次操作。

    木棒的初始形状为(XXXXXX......XXXXXX)。

    接下来m行,每行三个整数/字符,用空格隔开。第一个整数为1或2,表示操作的类型,若类型为1,则接下来一个整数x,一个字符C。若类型为2,接下来两个整数l,r。含义见题目描述。

    输出格式:

    对于每一个操作2,输出一行一个整数,表示对应询问的答案。

    输入输出样例

    输入样例#1: 复制
    4 4
    2 1 4
    2 2 4
    1 2 (
    2 2 4
    输出样例#1: 复制
    1
    0
    1

    说明

    对于30%的数据,1<=n,m<=1000

    对于100%的数据,1<=n,m<=200000

    by-orangebird

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