http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1301. JZPSTR(顾昱洲)
时间限制:5.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  你要对一个字符串进行三种操作:
  0. 在位置xi处插入一个字符串yi
  1. 删除位置[xi, yi)的字符串
  2. 查询位置[xi, yi)的字符串包含多少次给定的子串zi
输入格式
  第一行,一个整数T,表示操作个数。
  下面T行,每行第一个数pi,表示这个操作的类型:
  若pi=0,则接下来有一个整数xi和一个字符串yi,表示进行插入操作;
  若pi=1,则接下来有两个整数xi和yi,表示进行删除操作;
  若pi=2,则接下来有两个整数xi和yi,以及一个字符串zi,表示进行询问。

  字符串的下标从0开始(即第一个字符的下标为0)。
  初始时字符串为空。
  对于插入操作,插入后字符串yi的首字符的下标应为xi
  对于删除操作,删除的区间[xi, yi)为左闭右开区间;
  对于查询操作,询问的区间[xi, yi)为左闭右开区间。
  所有插入的和查询的字符串均不为空,且只包含0~9的字符。
  所有询问的区间和删除的区间均不为空。
  保证输入数据合法。

  对于"左闭右开区间"不理解的可以去看样例解释。
输出格式
  对每个询问操作,输出一行,表示这个询问的答案。
样例输入
8
0 0 894894894
2 0 2 894
2 0 9 894
0 2 6
2 0 9 64
2 0 9 894
1 2 6
2 0 6 894
样例输出
0
3
1
1
2
样例说明
  第一次操作后,字符串为894894894;
  第二次操作,询问的区间为89,不包含任何894;
  第三次操作,询问的区间为894894894,包含三个894;
  第四次操作后,字符串为8964894894;
  第五次操作,询问的区间为896489489,包含一个64;
  第六次操作,询问的区间为896489489,包含一个894;
  第七次操作后,字符串为894894;
  第八次操作,询问的区间为894894,包含两个894。
数据规模和约定
  50%的数据中,询问个数<=100 (不是操作个数)
  100%的数据中,插入总长度<=2000000,任何时刻字符串长度<=1000000,插入次数<=1001,删除次数<=1000,询问的zi的总长度<=10000