{"problem":{"name":"[LSOT-1] Crosspain","description":{"content":"令 $S_0=\\varnothing$，维护一个数据结构，要求支持以下操作： - `1 hoc s`，令 $S_i=S_{hoc}\\cup\\{s\\}$，其中 $s$ 是字符串（保证操作前 $s\\notin S_{hoc}$） . - `2 hoc s`，令 $S_i=S_{hoc}$，并查询 $S_i$ 中的所有字符串在给出的字符串 $s$ 中出现的次数之和 .","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":196608},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8451"},"statements":[{"statement_type":"Markdown","content":"令 $S_0=\\varnothing$，维护一个数据结构，要求支持以下操作：\n- `1 hoc s`，令 $S_i=S_{hoc}\\cup\\{s\\}$，其中 $s$ 是字符串（保证操作前 $s\\notin S_{hoc}$） .\n- `2 hoc s`，令 $S_i=S_{hoc}$，并查询 $S_i$ 中的所有字符串在给出的字符串 $s$ 中出现的次数之和 .\n\n## Input\n\n第一行包含一个正整数 $q$，表示询问次数 .\n\n接下来 $q$ 行，每行一个操作，格式见题目描述 .\n\n## Output\n\n对于每个操作 2，输出一行答案 .\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/xcjot9ob.png)\n\n## Note\n\n### 样例解释\n\n第三行中，询问版本 $0$ 中的串在 `abc` 中出现几次，因为版本 $0$ 为空，所以出现 $0$ 次 .\n\n第五行中，询问版本 $3$ 中的串在 `defg` 中出现几次，因为版本 $3$ 有字符串 `def`，所以出现 $1$ 次 .\n\n第六行中，询问版本 $1$ 中的串在 `abcd` 中出现几次，因为版本 $1$ 有字符串 `abc`，所以出现 $1$ 次 .\n\n### 数据范围及约定\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(10 pts)：} \\displaystyle \\sum|s_i|\\le 1000$；\n- $\\texttt{Subtask 2(20 pts)：}$所有添加的字符串长度相同；\n- $\\texttt{Subtask 3(20 pts)：}$所有添加的字符串只包含一种字符；\n- $\\texttt{Subtask 4(20 pts)：}q\\le 10^3$；\n- $\\texttt{Subtask 5(30 pts)：}$无特殊限制。\n\n对于全部数据，$1\\le q\\le  5\\times10^5$，$\\displaystyle 1\\le \\sum_i|s_i|\\le 10^6$ . 所有字符串仅含小写字母 .","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8451","tags":["洛谷原创","树论","AC 自动机"],"sample_group":[["5\n1 0 abc\n2 0 abc\n1 2 def\n2 3 defg\n2 1 abcd","0\n1\n1"]],"created_at":"2026-03-03 11:09:25"}}