| 题目名称 | 1771. [国家集训队2012]JZPSTR |
|---|---|
| 输入输出 | jzpstr.in/out |
| 难度等级 | ★★★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-10-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：18， 通过率：50% | ||||
 策 |
100 | 11.045 s | 7.85 MiB | C++ |
 Magolor |
100 | 21.588 s | 1.94 MiB | C++ |
 神威难藏于泪 |
100 | 24.110 s | 7.94 MiB | C++ |
|
Magolor |
100 | 24.372 s | 193.80 MiB | C++ |
|
Magolor |
100 | 24.437 s | 193.80 MiB | C++ |
 rewine |
100 | 25.341 s | 1.27 MiB | C++ |
|
Magolor |
100 | 26.353 s | 215.71 MiB | C++ |
|
Magolor |
100 | 29.341 s | 193.81 MiB | C++ |
|
Magolor |
100 | 39.829 s | 3.73 MiB | C++ |
|
rewine |
80 | 46.855 s | 1.27 MiB | C++ |
| 关于 JZPSTR 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
rewine
2018-10-17 18:39
4楼
| ||||
|
分块？假装数据中没有长度超过2048的询问。
因为它可能确实没有。 | ||||
|
回复 @winee :
%%%，orz,orz,orz,膜大佬，膜神犇，膜大佬，膜神犇，强强强，牛牛牛，厉害厉害厉害，给大佬低头，%%%  lalalala
2017-06-09 18:13
2楼
| ||||
|
给块状链表+后缀自动机跪烂……（题解都没看懂，我是不是不该去冬令营了?.....@cstdio)
 Asm.Def
2014-10-27 15:00
1楼
| ||||
JZPSTR(顾昱洲)
时间限制：5.0s 内存限制：256.0M
【试题来源】
2012信息学奥林匹克中国国家队训练
【问题描述】
你要对一个字符串进行三种操作：
0. 在位置x_i处插入一个字符串y_i
1. 删除位置[x_i, y_i)的字符串
2. 查询位置[x_i, y_i)的字符串包含多少次给定的子串z_i
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的字符。
所有询问的区间和删除的区间均不为空。
保证输入数据合法。
对于"左闭右开区间"不理解的可以去看样例解释。
下面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 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
3
1
1
2
样例说明
第一次操作后，字符串为894894894；
第二次操作，询问的区间为89，不包含任何894；
第三次操作，询问的区间为894894894，包含三个894；
第四次操作后，字符串为8964894894；
第五次操作，询问的区间为896489489，包含一个64；
第六次操作，询问的区间为896489489，包含一个894；
第七次操作后，字符串为894894；
第八次操作，询问的区间为894894，包含两个894。
第二次操作，询问的区间为89，不包含任何894；
第三次操作，询问的区间为894894894，包含三个894；
第四次操作后，字符串为8964894894；
第五次操作，询问的区间为896489489，包含一个64；
第六次操作，询问的区间为896489489，包含一个894；
第七次操作后，字符串为894894；
第八次操作，询问的区间为894894，包含两个894。
数据规模和约定
50%的数据中，询问个数<=100 (不是操作个数)
100%的数据中，插入总长度<=2000000，任何时刻字符串长度<=1000000，插入次数<=1001，删除次数<=1000，询问的z_i的总长度<=10000
100%的数据中，插入总长度<=2000000，任何时刻字符串长度<=1000000，插入次数<=1001，删除次数<=1000，询问的z_i的总长度<=10000