“终于逃出这该死的塔了”，1 x c，表示将 sx 修改为字符 c，保证 c 是小写字母；2 t l r，表示给出一个字符串 t，求 t 的所有子串和 sl...r 的匹配度之和，匹配度的定义见上，你决定玩一玩这个无聊的游戏，毕竟闲着也是闲着。
“终于逃出这该死的塔了”。 在塔的底部，你看到了一扇门，这是距你获得自由的最后一道屏障了。当然，打开这扇门是需要密码的，密码可抽象为一个只包含小写字母的字符串。你并不知道密码具体是多少，但通过某种方式得到了生成密码的模版串s，并且知道密码一定是模板串的一个子串。你会尝试若干次，每次将得到一个字符串 t 和一段区间 [l,r]，你会从选出 t 的一个子串去和 sl...r 匹配，定义两个字符串的匹配度为两个字符串的最长公共后缀长度 (最大的 x 使得两个串的后 x位相同)。你准备随机选出 t 的一个子串和 s 的这段区间匹配，并想知道匹配度的期望是多少，为了防止浮点误差，只需求出所有方案的匹配度的和即可。有时，你会发现你求的模板串出现了一些问题，需要对其中的一位进行修改，这个修改将会应用到以后的尝试上。更形式化地说，你需要维护以下两个操作： • 1 x c，表示将 sx (即 s 的第 x 个字符) 修改为字符 c，保证 c 是小写字母； • 2 t l r，表示给出一个字符串 t，求 t 的所有子串和 sl...r 的匹配度之和，匹配度的定义见上。 你决定玩一玩这个无聊的游戏，毕竟闲着也是闲着。
（图片来源网络，侵删）
