题目背景

“终于逃出这该死的塔了”。

题目描述

在塔的底部，你看到了一扇门，这是距你获得自由的最后一道屏障了。当然，打开这扇门是需要密码的，密码可抽象为一个只包含小写字母的字符串。你并不知道密码具体是多少，但通过某种方式得到了生成密码的模版串s，并且知道密码一定是模板串的一个子串。

你会尝试若干次，每次将得到一个字符串 $t$ 和一段区间 $[l,r]$，你会从选出 $t$ 的一个子串去和 $s_{l...r}$ 匹配，定义两个字符串的匹配度为两个字符串的最长公共后缀长度 (最大的 $x$ 使得两个串的后 $x$ 位相同)。你准备随机选出 $t$ 的一个子串和 $s$ 的这段区间匹配，并想知道匹配度的期望是多少，为了防止浮点误差，只需求出所有方案的匹配度的和即可。有时，你会发现你求的模板串出现了一些问题，需要对其中的一位进行修改，这个修改将会应用到以后的尝试上。

更形式化地说，你需要维护以下两个操作：

• 1 x c，表示将 $s_x$ (即 $s$ 的第 $x$ 个字符) 修改为字符 $c$，保证 $c$ 是小写字母；

• 2 t l r，表示给出一个字符串 $t$，求 $t$ 的所有子串和 $s_{l...r}$ 的匹配度之和，匹配度的定义见上。

你决定玩一玩这个无聊的游戏，毕竟闲着也是闲着。

输入格式

输入的第一行包含一个只包含小写字母的字符串 $s$，表示生成密码的模板。

第二行包含一个正整数 $n$，表示操作次数。

接下来 $n$ 行，每行形如 1 x c 或者 2 t l r，意义如题目所述。

输出格式

对于每组询问，输出一个整数，表示 $t$ 的所有子串和 $s_{l...r}$ 的匹配度之和。

bcca
4
2 acba 1 2
2 cab 1 4
1 2 b
2 bca 2 4

2
3
6

提示

定义 $S$ 为输入中的字符数量。

对于 $10 \%$ 的评测用例, $S \leq 100, n \leq 10$;

对于 $20 \%$ 的评测用例, $S \leq 1000, n \leq 100$;

对于 $30 \%$ 的评测用例, $S \leq 10000, n \leq 1000$;

对于 $50 \%$ 的评测用例, $S \leq 10^5, n \leq 10^5$;

对于 $70 \%$ 的评测用例, $S \leq 10^{6}$;

对于另 $14 \%$ 的评测用例, 没有修改操作;

对于所有评测用例, $S \leq 10^{7}, n \leq 10^{6}$ 。

保证输入合法, 数据有一定梯度。

保证每次询问的答案在 64 位有符号整数的范围内。

蓝桥杯 2019 年国赛 A 组 J 题。