#PQZ1038x5037. 回文
回文
回文
题目描述
标题: 回文 - Problem - QOJ.ac
#5037. 回文
The problem was used in the following contests:
题目描述
给定一个只含小写字母的字符串 S,有 Q 次操作,操作有以下两种:
1 i c:将 Si 修改为 c(1≤i≤|S|,c 是小写字母)。2 l r:查询 S[l...r] 有多少回文后缀(1≤l≤r≤|S|)。
输入格式
第一行一个只含小写字母的字符串 S(|S|≤2×105)。
第二行一个整数 Q(Q≤2×105),表示操作次数。
接下来 Q 行,每行是一个操作。
本题强制在线,如果是操作 1,那么要将输入的 i 异或上 lastans,如果是操作 2,那么要将 l 和 r 都异或上 lastans。lastans 是上一次操作 2 的答案,如果没有上一次操作 2,则 lastans=0。
输出格式
对每个操作 2 输出一行答案。
样例
Input1
abbbaabbba
7
2 10 10
1 9 a
1 11 b
2 6 9
1 9 a
1 6 a
2 2 6
Output1
1
1
3
解密后的输入为:
abbbaabbba
7
2 10 10
1 8 a
1 10 b
2 7 8
1 8 a
1 7 a
2 3 7
对于第 1 个操作,查询字符串为:a,回文后缀有 a。
对于第 4 个操作,查询字符串为:ba,回文后缀有 a。
对于第 7 个操作,查询字符串为:bbaaa,回文后缀有 a、aa 和 aaa。
Input2
abaabaabbaabbaabaaba
10
2 15 19
2 8 18
2 6 15
2 14 13
2 8 15
2 1 16
2 14 21
2 9 12
2 4 17
2 5 12
Output2
2
2
3
1
2
4
2
2
3
4
解密后的输入为:
abaabaabbaabbaabaaba
10
2 15 19
2 10 16
2 4 13
2 13 14
2 9 14
2 3 18
2 10 17
2 11 14
2 6 19
2 6 15
数据范围
对所有数据满足:1≤|S|,Q≤2×105。
详细子任务附加限制及分值如下表所示:
子任务编号 |S|≤ |Q|≤ 特殊性质 分值 子任务依赖 1 5×103 5×103 / 10 / 2 2×105 2×105 没有操作 1 10 3 Si 和 c 在 {a,b} 中均匀独立随机,操作 1 中 i 在 [1,|S|] 中均匀独立随机 10 4 操作 2 中 l=1,r=|S| 10 5 / 30 1 6 30 1∼5
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
官方测试点 25 个;落地 2 个;时限 8.0s,内存 1024MB。
样例
样例 1
abbbaabbba
7
2 10 10
1 9 a
1 11 b
2 6 9
1 9 a
1 6 a
2 2 6
1
1
3
样例 2
abaabaabbaabbaabaaba
10
2 15 19
2 8 18
2 6 15
2 14 13
2 8 15
2 1 16
2 14 21
2 9 12
2 4 17
2 5 12
2
2
3
1
2
4
2
2
3
4
数据来源:QOJ 公开题包官方 .in/.out;本题落地 2 个测试点,QOJ 元数据标注官方共 25 点,覆盖级别:部分公开样例级数据。时限 8.0s,内存 1024MB。按 Hydro 默认逐字节比对判定。