OpenJudge

1001:[顾昱洲]JZPSTR

总时间限制:
100000ms
单个测试点时间限制:
1000ms
内存限制:
262144kB
描述

你要对一个字符串进行三种操作:
0. 在位置x_i处插入一个字符串y_i
1. 删除位置[x_i, y_i)的字符串
2. 查询位置[x_i, y_i)的字符串包含多少次给定的子串z_i

输入
第一行,一个整数T,表示操作个数。
下面T行,每行第一个数p_i,表示这个操作的类型:
若p_i=0,则接下来有一个整数x_i和一个字符串y_i,表示进行插入操作;
若p_i=1,则接下来有两个整数x_i和y_i,表示进行删除操作;
若p_i=2,则接下来有两个整数x_i和y_i,以及一个字符串z_i,表示进行询问。
字符串的下标从0开始(即第一个字符的下标为0)。
初始时字符串为空。
对于插入操作,插入后字符串y_i的首字符的下标应为x_i;
对于删除操作,删除的区间[x_i, y_i)为左闭右开区间;
对于查询操作,询问的区间[x_i, y_i)为左闭右开区间。
所有插入的和查询的字符串均不为空,且只包含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
提示
50%的数据中,询问个数<=100 (不是操作个数)
100%的数据中,插入总长度<=2000000,任何时刻字符串长度<=1000000,插入次数<=1001,删除次数<=1000,询问的z_i的总长度<=10000
全局题号
5092
添加于
2012-07-13
提交次数
0
尝试人数
0
通过人数
0