[LSOT-1] Crosspain

Luogu

IDLGP8451

Time1000ms

Memory192MB

DifficultyP6

洛谷原创树论AC 自动机

令 $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$ 中出现的次数之和 . ## Input 第一行包含一个正整数 $q$，表示询问次数 . 接下来 $q$ 行，每行一个操作，格式见题目描述 . ## Output 对于每个操作 2，输出一行答案 . [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/xcjot9ob.png) ## Note ### 样例解释第三行中，询问版本 $0$ 中的串在 `abc` 中出现几次，因为版本 $0$ 为空，所以出现 $0$ 次 . 第五行中，询问版本 $3$ 中的串在 `defg` 中出现几次，因为版本 $3$ 有字符串 `def`，所以出现 $1$ 次 . 第六行中，询问版本 $1$ 中的串在 `abcd` 中出现几次，因为版本 $1$ 有字符串 `abc`，所以出现 $1$ 次 . ### 数据范围及约定 **「本题采用捆绑测试」** - $\texttt{Subtask 1(10 pts)：} \displaystyle \sum|s_i|\le 1000$； - $\texttt{Subtask 2(20 pts)：}$所有添加的字符串长度相同； - $\texttt{Subtask 3(20 pts)：}$所有添加的字符串只包含一种字符； - $\texttt{Subtask 4(20 pts)：}q\le 10^3$； - $\texttt{Subtask 5(30 pts)：}$无特殊限制。对于全部数据，$1\le q\le 5\times10^5$，$\displaystyle 1\le \sum_i|s_i|\le 10^6$ . 所有字符串仅含小写字母 .

Samples

Input #1

5
1 0 abc
2 0 abc
1 2 def
2 3 defg
2 1 abcd

Output #1

0
1
1

API Response (JSON)

{
  "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第一行包含一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments