[JRKSJ R7] Clock Paradox

给你一个字符串 $S$，设 $S=\overline{s_1s_2\dots s_n}$。 有一个字符串 $T$，初始时 $T=S$，你可以进行若干次操作，每次操作可以选取 $S$ 一个子串并插入到 $T$ 的任意位置。 你希望经过若干次操作后，$T=\overline{s_1s_1s_2s_2\dots s_ns_n}$，定义 $f(S)$ 为满足此条件所需的最少的操作次数。 此外，字符串 $S$ 还会发生一些改变。具体地，有 $q$ 次修改操作，每次修改操作会给出 $p$ 和 $\texttt{c}$，表示令 $s_p\gets \texttt{c}$。$\texttt{c}$ 表示任意一个小写字母，而并非 ASCII 为 $99$ 的字符。 你需要在最开始和每次修改后求出 $f(S)$ 的值。 ## Input 第一行一个整数 $q$ 表示修改次数。\ 第二行仅由小写字母构成的字符串 $S$。\ 接下来 $q$ 行，每行一个整数 $p$ 和一个小写字母 $\texttt{c}$ 表示一次修改。 ## Output 共有 $q+1$ 行，每行一个整数表示答案。 [samples] ## Background  一分钟后的出题人阻止了这个时刻的出题人写一个有趣的题目背景。 （题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。） ## Note Idea：cyffff，Solution：cyffff，Code：cyffff，Data：cyffff **Clock Paradox - WyvernP (Insane12.6)** **本题输入输出文件较大，请使用恰当的输入输出方式。** ### 提示 称字符串 $A$ 是字符串 $S$ 的子串当且仅当存在 $1\le l\le r\le |S|$ 使得 $A=\overline{s_ls_{l+1}\dots s_{r}}$。 ### 样例解释 所有修改前，$f(S)$ 的计算方法如下： 初始时，$S=T=\texttt{aabc}$。 第一次操作，选取 $S$ 的子串 $\texttt{aa}$，插入到 $T$ 的最前端，操作后 $T=\texttt{aaaabc}$。 第二次操作，选取 $S$ 的子串 $\texttt{bc}$，插入到 $T$ 的第 $5$ 个字符后，操作后 $T=\texttt{aaaabbcc}$，符合要求。 经过一次修改、两次修改后的 $S$ 分别等于 $\texttt{abbc}$ 和 $\texttt{abbb}$，这两次修改后 $f(S)$ 分别是 $2$ 和 $1$。 ### 数据规模 本题采用捆绑测试。 | $\text{Subtask}$ | $\vert S\vert\le$ | $q\le$ | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $0$ | $10$ | | $2$ | $10^4$ | $10^4$ | $20$ | | $3$ | $5\times10^5$ | $0$ | $20$ | | $4$ | $5\times10^5$ | $5\times 10^5$ | $20$ | | $5$ | $3\times10^6$ | $3\times 10^6$ | $30$ | 对于 $100\%$ 的数据，$1\le|S|\le3\times10^6$，$0\le q\le 3\times10^6$，保证 $S$ 仅由小写字母构成，保证 $\texttt{c}$ 为单个小写字母。