F. String Set Queries

Codeforces

IDCF710F

Time3000ms

Memory768MB

Difficulty—

brute forcedata structureshashinginteractivestring suffix structuresstrings

English · Original

Chinese · Translation

Formal · Original

You should process _m_ queries over a set _D_ of strings. Each query is one of three kinds: 1. Add a string _s_ to the set _D_. It is guaranteed that the string _s_ was not added before. 2. Delete a string _s_ from the set _D_. It is guaranteed that the string _s_ is in the set _D_. 3. For the given string _s_ find the number of occurrences of the strings from the set _D_. If some string _p_ from _D_ has several occurrences in _s_ you should count all of them. Note that you should solve the problem in _online_ mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query of the third type. Use functions _fflush_ in _C++_ and _BufferedWriter.flush_ in _Java_ languages after each writing in your program. ## Input The first line contains integer _m_ (1 ≤ _m_ ≤ 3·105) — the number of queries. Each of the next _m_ lines contains integer _t_ (1 ≤ _t_ ≤ 3) and nonempty string _s_ — the kind of the query and the string to process. All strings consist of only lowercase English letters. The sum of lengths of all strings in the input will not exceed 3·105. ## Output For each query of the third kind print the only integer _c_ — the desired number of occurrences in the string _s_. [samples]

你需要对一组字符串集合 #cf_span[D] 处理 #cf_span[m] 个查询。每个查询属于以下三种类型之一：请注意，你必须以 _在线_ 模式解决此问题。这意味着你不能一次性读取全部输入。你只能在输出上一个第三类查询的答案后，才能读取下一个查询。请在程序中每次输出后调用 _fflush_ 函数（C++）或 _BufferedWriter.flush_（Java）。第一行包含整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 3·10^5]）——查询的数量。接下来的 #cf_span[m] 行中，每行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 3]）和一个非空字符串 #cf_span[s]，分别表示查询类型和待处理的字符串。所有字符串仅由小写英文字母组成。输入中所有字符串的长度总和不超过 #cf_span[3·10^5]。对于每个第三类查询，请输出一个整数 #cf_span[c] —— 字符串 #cf_span[s] 中所需的出现次数。 ## Input 第一行包含整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 3·10^5]）——查询的数量。接下来的 #cf_span[m] 行中，每行包含一个整数 #cf_span[t]（#cf_span[1 ≤ t ≤ 3]）和一个非空字符串 #cf_span[s]，分别表示查询类型和待处理的字符串。所有字符串仅由小写英文字母组成。输入中所有字符串的长度总和不超过 #cf_span[3·10^5]。 ## Output 对于每个第三类查询，请输出一个整数 #cf_span[c] —— 字符串 #cf_span[s] 中所需的出现次数。 [samples]

**Definitions** Let $ m \in \mathbb{Z} $ be the number of queries. Let $ D \subseteq \Sigma^* $ be a dynamic set of strings over $ \Sigma = \{a, b, \dots, z\} $, initially empty. Let $ Q = (q_1, q_2, \dots, q_m) $ be a sequence of queries, where each $ q_i = (t_i, s_i) $: - $ t_i \in \{1, 2, 3\} $: query type, - $ s_i \in \Sigma^+ $: a nonempty string. **Constraints** 1. $ 1 \leq m \leq 3 \cdot 10^5 $ 2. $ \sum_{i=1}^m |s_i| \leq 3 \cdot 10^5 $ 3. All $ s_i $ consist only of lowercase English letters. **Objective** Process queries online: - If $ t_i = 1 $: insert $ s_i $ into $ D $. - If $ t_i = 2 $: remove one occurrence of $ s_i $ from $ D $ (guaranteed to exist). - If $ t_i = 3 $: output the number of times $ s_i $ occurs in $ D $. For each query of type 3, output $ c_i = |\{ j \in \{1, \dots, i\} \mid t_j = 1 \land s_j = s_i \}| - |\{ j \in \{1, \dots, i\} \mid t_j = 2 \land s_j = s_i \}| $.

Samples

Input #1

5
1 abc
3 abcabc
2 abc
1 aba
3 abababc

Output #1

2
2

Input #2

10
1 abc
1 bcd
1 abcd
3 abcd
2 abcd
3 abcd
2 bcd
3 abcd
2 abc
3 abcd

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. String Set Queries",
    "description": {
      "content": "You should process _m_ queries over a set _D_ of strings. Each query is one of three kinds: 1.  Add a string _s_ to the set _D_. It is guaranteed that the string _s_ was not added before. 2.  Delete ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 786432
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF710F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You should process _m_ queries over a set _D_ of strings. Each query is one of three kinds:\n\n1.  Add a string _s_ to the set _D_. It is guaranteed that the string _s_ was not added before.\n2.  Delete ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你需要对一组字符串集合 #cf_span[D] 处理 #cf_span[m] 个查询。每个查询属于以下三种类型之一：\n\n请注意，你必须以 _在线_ 模式解决此问题。这意味着你不能一次性读取全部输入。你只能在输出上一个第三类查询的答案后，才能读取下一个查询。请在程序中每次输出后调用 _fflush_ 函数（C++）或 _BufferedWriter.flush_（Java）。\n\n第一行包含整数 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ m \\in \\mathbb{Z} $ be the number of queries.  \nLet $ D \\subseteq \\Sigma^* $ be a dynamic set of strings over $ \\Sigma = \\{a, b, \\dots, z\\} $, initially empty.  \nLet $ Q = (q_1,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments