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