Jamie and To-do List

题意翻译

## 题目描述 “为什么我要完成这么多作业？” Jamie 正忙于他的学校生活。 他开始忘记他必须做的作业。他决定把这些事情写在 To-Do List 上。 他为他的每项任务分配一个价值优先级(较低的价值意味着更重要)，这样他就可以决定他需要花更多的时间在哪个任务上。 几天后，Jamie 发现名单太大了，他甚至不能自己管理名单！由于您是 Jamie 的好朋友，请帮助他编写一个程序来支持待办事项列表中的以下操作: `set ai xi`：设置任务 $a_i$ 的优先级为 $x_i$，如果该列表中没有出现则加入该任务。 `remove a_i`：删除该任务。 `query a_i`：求优先级比 $a_i$ 小的任务个数，如果没有则输出 $-1$。 `undo sum`：删除此次操作之前的 $sum$ 此操作。 在 Day 0，To-Do List 为空，在接下来 $Q$ 个日子内，Jamie 都会在四个操作中任选一个执行。 对于每个询问操作，输出对应的答案。 ## 输入格式 第一行是一个整数 $Q$。 接下来的 $Q$ 行为任一个操作，第 $i$ 为第 $i$ 天的操作。 **保证最后一行是询问操作。** ## 输出格式 对于所有的查询操作，输出对应的答案。 ## 数据范围 保证输入的字符串由小写字符构成，设其长度为 $len$，则 $1\leq len\leq15$。 $1\le Q\le10^5$，并且保证对于所有的 undo 操作，$1\le sum $＜$~5$。

题目描述

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 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. After 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: - $ 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} $ . - $ remove\ a_{i} $ — Remove assignment $ a_{i} $ from the to-do list if it is present in it. - $ 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. - $ undo\ d_{i} $ — Undo all changes that have been made in the previous $ d_{i} $ days (not including the day of this operation) At 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.

输入输出格式

输入格式

The first line consists of a single integer $ q $ $ (1<=q<=10^{5}) $ — the number of operations. The 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: The first word in the line indicates the type of operation. It must be one of the following four: set, remove, query, undo. - If it is a set operation, a string $ a_{i} $ and an integer $ x_{i} $ follows $ (1<=x_{i}<=10^{9}) $ . $ a_{i} $ is the assignment that need to be set to priority $ x_{i} $ . - If it is a remove operation, a string $ a_{i} $ follows. $ a_{i} $ is the assignment that need to be removed. - If it is a query operation, a string $ a_{i} $ follows. $ a_{i} $ is the assignment that needs to be queried. - 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. All assignment names $ a_{i} $ only consists of lowercase English letters and have a length $ 1<=|a_{i}|<=15 $ . It is guaranteed that the last operation is a query operation.

输出格式

For 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. Interaction If 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. For 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: - C: fflush(stdout); - C++: cout « flush; - Java: System.out.flush();

输入输出样例

输入样例 #1

8
set chemlabreport 1
set physicsexercise 2
set chinesemockexam 3
query physicsexercise
query chinesemockexam
remove physicsexercise
query physicsexercise
query chinesemockexam

输出样例 #1

1
2
-1
1

输入样例 #2

8
set physicsexercise 2
set chinesemockexam 3
set physicsexercise 1
query physicsexercise
query chinesemockexam
undo 4
query physicsexercise
query chinesemockexam

输出样例 #2

0
1
0
-1

输入样例 #3

5
query economicsessay
remove economicsessay
query economicsessay
undo 2
query economicsessay

输出样例 #3

-1
-1
-1

输入样例 #4

5
set economicsessay 1
remove economicsessay
undo 1
undo 1
query economicsessay

输出样例 #4

-1