QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 1024 MB Total points: 100
[+2]

# 5037. 回文

Statistics

题目描述

给定一个只含小写字母的字符串 S,有 Q 次操作,操作有以下两种:

  • 1 i c:将 Si 修改为 c1i|S|c 是小写字母)。
  • 2 l r:查询 S[l...r] 有多少回文后缀(1lr|S|)。

输入格式

第一行一个只含小写字母的字符串 S|S|2×105)。

第二行一个整数 QQ2×105),表示操作次数。

接下来 Q 行,每行是一个操作。

本题强制在线,如果是操作 1,那么要将输入的 i 异或上 lastans,如果是操作 2,那么要将 lr 都异或上 lastanslastans 是上一次操作 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|,Q2×105

详细子任务附加限制及分值如下表所示:

子任务编号 |S| |Q| 特殊性质 分值 子任务依赖
1 5×103 5×103 / 10 /
2 2×105 2×105 没有操作 1 10
3 Sic{a,b} 中均匀独立随机,操作 1i[1,|S|] 中均匀独立随机 10
4 操作 2l=1,r=|S| 10
5 / 30 1
6 30 15