{"problem":{"name":"D. Jamie and To-do List","description":{"content":"_Why I have to finish so many assignments???_ Jamie is getting very busy with his school life. He starts to forget the assignments that he has to do. He decided to write the things down on a to-do li","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF916D"},"statements":[{"statement_type":"Markdown","content":"_Why I have to finish so many assignments???_\n\nJamie is getting very busy with his school life. He starts to forget the assignments that he has to do. He decided to write the things down on a to-do list. He assigns a value _priority_ for each of his assignment **(lower value means more important)** so he can decide which he needs to spend more time on.\n\nAfter a few days, Jamie finds out the list is too large that he can't even manage the list by himself! As you are a good friend of Jamie, help him write a program to support the following operations on the to-do list:\n\n*   _set_ _a__i_ _x__i_ — Add assignment _a__i_ to the to-do list if it is not present, and set its _priority_ to _x__i_. If assignment _a__i_ is already in the to-do list, its _priority_ **is changed** to _x__i_.\n*   _remove_ _a__i_ — Remove assignment _a__i_ from the to-do list if it is present in it.\n*   _query_ _a__i_ — Output the number of assignments that are more important (have a **smaller** _priority_ value) than assignment _a__i_, so Jamie can decide a better schedule. Output  - 1 if _a__i_ is not in the to-do list.\n*   _undo_ _d__i_ — Undo all changes that have been made in the previous _d__i_ days (not including the day of this operation)\n\nAt day 0, the to-do list is empty. In each of the following _q_ days, Jamie will do **exactly one** out of the four operations. If the operation is a _query_, you should **output the result of the query before proceeding to the next day**, or poor Jamie cannot make appropriate decisions.\n\n## Input\n\nThe first line consists of a single integer _q_ (1 ≤ _q_ ≤ 105) — the number of operations.\n\nThe following _q_ lines consists of the description of the operations. The _i_\\-th line consists of the operation that Jamie has done in the _i_\\-th day. The query has the following format:\n\nThe first word in the line indicates the type of operation. It must be one of the following four: _set_, _remove_, _query_, _undo_.\n\n*   If it is a _set_ operation, a string _a__i_ and an integer _x__i_ follows (1 ≤ _x__i_ ≤ 109). _a__i_ is the assignment that need to be set to _priority_ _x__i_.\n*   If it is a _remove_ operation, a string _a__i_ follows. _a__i_ is the assignment that need to be removed.\n*   If it is a _query_ operation, a string _a__i_ follows. _a__i_ is the assignment that needs to be queried.\n*   If it is a _undo_ operation, an integer _d__i_ follows (0 ≤ _d__i_ < _i_). _d__i_ is the number of days that changes needed to be undone.\n\nAll assignment names _a__i_ only consists of lowercase English letters and have a length 1 ≤ |_a__i_| ≤ 15.\n\nIt is guaranteed that the last operation is a _query_ operation.\n\n## Output\n\nFor each _query_ operation, output a single integer — the number of assignments that have a priority lower than assignment _a__i_, or  - 1 if _a__i_ is not in the to-do list.\n\n[samples]\n\n## Interaction\n\nIf the operation is a _query_, you **should** output the result of the query and flush the output stream before proceeding to the next operation. Otherwise, you may get the verdict _Idleness Limit Exceed_.\n\nFor flushing the output stream, please refer to the documentation of your chosen programming language. The flush functions of some common programming languages are listed below:\n\n*   C: _fflush(stdout);_\n*   C++: _cout « flush;_\n*   Java: _System.out.flush();_","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_为什么我得完成这么多作业啊？_\n\nJamie 的学校生活变得非常忙碌。他开始忘记自己需要完成的作业。于是他决定把事情写在待办清单上，并为每项作业分配一个 _优先级_ 值（值越小表示越重要），以便决定哪些作业需要花更多时间。\n\n几天后，Jamie 发现清单太长了，以至于他自己都难以管理！作为 Jamie 的好朋友，请你帮他写一个程序，支持对待办清单进行以下操作：\n\n在第 #cf_span[0] 天，待办清单为空。在接下来的 #cf_span[q] 天中，Jamie 每天恰好执行以下四种操作之一。如果操作是 #cf_span[query]，你必须在进入下一天之前 *输出该查询的结果*，否则可怜的 Jamie 将无法做出合适的决策。\n\n第一行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 操作的数量。\n\n接下来的 #cf_span[q] 行描述了这些操作。第 #cf_span[i] 行描述了 Jamie 在第 #cf_span[i] 天执行的操作。查询操作的格式如下：\n\n每行的第一个单词表示操作类型，必须是以下四种之一：_set_、_remove_、_query_、_undo_。\n\n所有作业名称 #cf_span[ai] 仅由小写英文字母组成，长度满足 #cf_span[1 ≤ |ai| ≤ 15]。\n\n保证最后一个操作是 _query_ 操作。\n\n对于每个 _query_ 操作，输出一个整数 —— 优先级低于作业 #cf_span[ai] 的作业数量，如果 #cf_span[ai] 不在待办清单中，则输出 #cf_span[ - 1]。\n\n如果操作是 #cf_span[query]，你 *必须* 输出查询结果并刷新输出流，然后再进行下一个操作。否则，你可能会得到 _Idleness Limit Exceed_ 的评测结果。\n\n关于刷新输出流，请参考你所选编程语言的文档。以下是一些常见编程语言的刷新函数：\n\n## Input\n\n第一行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 操作的数量。接下来的 #cf_span[q] 行描述了这些操作。第 #cf_span[i] 行描述了 Jamie 在第 #cf_span[i] 天执行的操作。操作格式如下：\n\n每行的第一个单词表示操作类型，必须是以下四种之一：_set_、_remove_、_query_、_undo_。\n\n如果是 _set_ 操作，后面跟一个字符串 #cf_span[ai] 和一个整数 #cf_span[xi] #cf_span[(1 ≤ xi ≤ 109)]，表示将作业 #cf_span[ai] 的优先级设置为 #cf_span[xi]。\n\n如果是 _remove_ 操作，后面跟一个字符串 #cf_span[ai]，表示移除作业 #cf_span[ai]。\n\n如果是 _query_ 操作，后面跟一个字符串 #cf_span[ai]，表示查询作业 #cf_span[ai]。\n\n如果是 _undo_ 操作，后面跟一个整数 #cf_span[di] #cf_span[(0 ≤ di < i)]，表示需要撤销过去 #cf_span[di] 天内的所有变更。\n\n所有作业名称 #cf_span[ai] 仅由小写英文字母组成，长度满足 #cf_span[1 ≤ |ai| ≤ 15]。\n\n保证最后一个操作是 _query_ 操作。\n\n## Output\n\n对于每个 _query_ 操作，输出一个整数 —— 优先级低于作业 #cf_span[ai] 的作业数量，如果 #cf_span[ai] 不在待办清单中，则输出 #cf_span[ - 1]。\n\n[samples]\n\n## Interaction\n\n如果操作是 #cf_span[query]，你 *必须* 输出查询结果并刷新输出流，然后再进行下一个操作。否则，你可能会得到 _Idleness Limit Exceed_ 的评测结果。\n\n关于刷新输出流，请参考你所选编程语言的文档。以下是一些常见编程语言的刷新函数：\n\nC: _fflush(stdout);_\nC++: _cout << flush;_\nJava: _System.out.flush();_","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n- Let $ L $ be a dynamic multiset of assignments, where each assignment is a tuple $ (a_i, p_i) $, with $ a_i \\in \\Sigma^{1..15} $ (assignment name, lowercase English letters) and $ p_i \\in \\mathbb{Z}^+ $ (priority, lower value = more important).\n- Let $ Q $ be a sequence of $ q $ operations ($ 1 \\leq q \\leq 10^5 $).\n\n**Operations:**\n1. **set $ a_i $ $ p_i $:**  \n   Insert or update assignment $ a_i $ with priority $ p_i $:  \n   $ L \\leftarrow L \\cup \\{(a_i, p_i)\\} $ (if $ a_i $ exists, update its priority to $ p_i $).\n\n2. **remove $ a_i $:**  \n   Remove assignment $ a_i $ from $ L $, if present:  \n   $ L \\leftarrow L \\setminus \\{(a_i, p) \\mid p \\in \\mathbb{Z}^+\\} $.\n\n3. **query $ a_i $:**  \n   If $ a_i \\notin \\text{dom}(L) $, output $ -1 $.  \n   Otherwise, output:  \n   $$\n   \\left| \\left\\{ (a_j, p_j) \\in L \\mid p_j < p_i \\right\\} \\right|\n   $$\n   where $ p_i $ is the priority of $ a_i $ in $ L $.\n\n4. **undo:**  \n   Revert the state of $ L $ to the state it had immediately before the most recent operation (i.e., maintain a versioned history of $ L $; undo the last non-undo operation).\n\n**Initial State:**  \n$ L_0 = \\emptyset $\n\n**Constraints:**  \n- The last operation is guaranteed to be a `query`.  \n- All operations are performed sequentially; `undo` affects the state of $ L $, not the history of operations.  \n- For each `query`, output the result immediately and flush the output stream.\n\n**Objective:**  \nProcess each operation in sequence, maintaining the state of $ L $ and correctly answering each `query` as defined.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF916D","tags":["data structures","interactive","trees"],"sample_group":[["8\nset chemlabreport 1\nset physicsexercise 2\nset chinesemockexam 3\nquery physicsexercise\nquery chinesemockexam\nremove physicsexercise\nquery physicsexercise\nquery chinesemockexam","1\n2\n-1\n1"],["8\nset physicsexercise 2\nset chinesemockexam 3\nset physicsexercise 1\nquery physicsexercise\nquery chinesemockexam\nundo 4\nquery physicsexercise\nquery chinesemockexam","0\n1\n0\n-1"],["5\nquery economicsessay\nremove economicsessay\nquery economicsessay\nundo 2\nquery economicsessay","\\-1\n-1\n-1"],["5\nset economicsessay 1\nremove economicsessay\nundo 1\nundo 1\nquery economicsessay","\\-1"]],"created_at":"2026-03-03 11:00:39"}}