【NOIP模拟赛】高级打字机

2014年3月15日2,0949

高级打字机(type.cpp/c/pas)

【题目描述】

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能,那就是它具备撤销功能,厉害吧。

请为这种高级打字机设计一个程序,支持如下3种操作:

1.T x:在文章末尾打下一个小写字母x。(type操作)

2.U x:撤销最后的x次修改操作。(Undo操作)

(注意Query操作并不算修改操作)

3.Q x:询问当前文章中第x个字母并输出。(Query操作)

文章一开始可以视为空串。

 

【输入格式】

第1行:一个整数n,表示操作数量。

以下n行,每行一个命令。保证输入的命令合法。

 

【输出格式】

每行输出一个字母,表示Query操作的答案。

 

【样例输入】

7

T a

T b

T c

Q 2

U 2

T c

Q 2

【样例输出】

b

c

【数据范围】

对于40%的数据 n<=200;

对于100%的数据 n<=100000;保证Undo操作不会撤销Undo操作。

<高级挑战>

对于200%的数据 n<=100000;Undo操作可以撤销Undo操作。

<IOI挑战>

必须使用在线算法完成该题。

题解

蒟蒻只会前100模拟

 

 

  • Mektpoy2014年3月16日 下午8:44 回复

    在线rope秒杀 如果离线的话发现只是个N-1条边的二元关系 在一颗树上面暴力就可以了

    #1  
  • Falsyta2014年3月17日 下午8:46 回复

    如果第一个Undo撤消了几个Type,第二个Undo撤消了第一个Undo,第三个Undo如果包含了前两个怎么办……………………

    #2  
    • hzwer2014年3月17日 下午8:51 回复
      admin

      这个我还没写出来。。似乎是建树乱搞。。

      #21
      • Falsyta2014年3月18日 上午7:51 回复

        …………不会矛盾么?那会是什么效果……………………

        #22
        • 骏马奔腾2014年3月18日 上午10:18 回复

          orz

          #23
        • hzwer2014年3月18日 上午10:34 回复
          admin

          搞出字典树在树上倍增,乱搞。。

          #23
          • Falsyta2014年3月18日 下午9:47

            怎么说呢………………我的意思其实是第三个Undo的逻辑不会自相矛盾么…………首先要撤销第二个Undo对第一个Undo的撤销操作…………也就是恢复第一个Undo,但同时它还要撤销第一个Undo?

            #24
          • hzwer2014年3月18日 下午10:55
            admin

            对,等于是回到了第一个undo前

            #24
          • Falsyta2014年3月19日 上午7:29

            ………………这题目真可怕…………我逻辑已经完全混乱了……………………(话说这主题我倒是见过…………但是看到默认显示的图片以后………………果断换了一个更加正常向的…………………………)

            #24