A16117 | Rollbacks (Easy Version)
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
This is an easy version of this problem. The only difference between the versions is that you have to solve the hard version in online mode. You can make hacks only if both versions of the problem are solved.
You have an array $a$ , which is initially empty. You need to process queries of the following types:
- + $x$ — add the integer $x$ to the end of the array $a$ .
- - $k$ — remove the last $k$ numbers from the array $a$ .
- ! — roll back the last active change (i.e., make the array $a$ the way it was before the change). In this problem, only queries of the first two types (+ and -) are considered as changes.
- ? — find the number of distinct numbers in the array $a$ .
You have an array $a$ , which is initially empty. You need to process queries of the following types:
- + $x$ — add the integer $x$ to the end of the array $a$ .
- - $k$ — remove the last $k$ numbers from the array $a$ .
- ! — roll back the last active change (i.e., make the array $a$ the way it was before the change). In this problem, only queries of the first two types (+ and -) are considered as changes.
- ? — find the number of distinct numbers in the array $a$ .
输入格式
The first line contains an integer $q$ ( $1 \leq q \leq 10^6$ ) — the number of queries.
The next $q$ lines contain the queries as described above.
It is guaranteed that
- in the queries of the first type, $1 \le x \le 10^6$ ;
- in the queries of the second type, $k \ge 1$ and $k$ does not exceed the current length of the array $a$ ;
- at the moment of the queries of the third type, there is at least one query of the first or of the second type that can be rolled back.
It is also guaranteed that the number of queries of the fourth type (?) does not exceed $10^5$ .
The next $q$ lines contain the queries as described above.
It is guaranteed that
- in the queries of the first type, $1 \le x \le 10^6$ ;
- in the queries of the second type, $k \ge 1$ and $k$ does not exceed the current length of the array $a$ ;
- at the moment of the queries of the third type, there is at least one query of the first or of the second type that can be rolled back.
It is also guaranteed that the number of queries of the fourth type (?) does not exceed $10^5$ .
输出格式
For each query of the fourth type output one integer — the number of distinct elements in array $a$ at the moment of query.
输入输出样例
输入 #1
10 + 1 + 2 + 2 ? ! + 3 - 2 ? + 1 ?
输出 #1
2 1 1
输入 #2
6 + 1 + 1000000 ? ! ! ?
输出 #2
2 0
In the first example array $a$ changes as follows:
1. After the first query, $a=[1]$ .
2. After the second query, $a=[1,2]$ .
3. After the third query, $a=[1,2,2]$ .
4. At the moment of the fourth query, there are $2$ distinct intergers in the array $a$ : $1$ and $2$ .
5. After the fifth query, $a=[1,2]$ (rolled back the change + 2).
6. After the sixth query, $a=[1,2,3]$ .
7. After the seventh query, $a=[1]$ .
8. At the moment of the eigth query, there is only one $1$ in the array $a$ .
9. After the ninth query, $a=[1,1]$ .
10. At the moment of the tenth query, there are only two $1$ in the array $a$ .
In the second example array $a$ changes as follows:
1. After the first query, $a=[1]$ .
2. After the second query, $a=[1,1\,000\,000]$ .
3. At the moment of the third query, there are $2$ distinct intergers in the array $a$ : $1$ and $1\,000\,000$ .
4. After the fourth query, $a=[1]$ (rolled back the change + 1000000).
5. After the fifth query, $a=[]$ (rolled back the change + 1).
6. At the moment of the sixth query, there are no integers in the array $a$ , so the answer to this query is $0$ .
1. After the first query, $a=[1]$ .
2. After the second query, $a=[1,2]$ .
3. After the third query, $a=[1,2,2]$ .
4. At the moment of the fourth query, there are $2$ distinct intergers in the array $a$ : $1$ and $2$ .
5. After the fifth query, $a=[1,2]$ (rolled back the change + 2).
6. After the sixth query, $a=[1,2,3]$ .
7. After the seventh query, $a=[1]$ .
8. At the moment of the eigth query, there is only one $1$ in the array $a$ .
9. After the ninth query, $a=[1,1]$ .
10. At the moment of the tenth query, there are only two $1$ in the array $a$ .
In the second example array $a$ changes as follows:
1. After the first query, $a=[1]$ .
2. After the second query, $a=[1,1\,000\,000]$ .
3. At the moment of the third query, there are $2$ distinct intergers in the array $a$ : $1$ and $1\,000\,000$ .
4. After the fourth query, $a=[1]$ (rolled back the change + 1000000).
5. After the fifth query, $a=[]$ (rolled back the change + 1).
6. At the moment of the sixth query, there are no integers in the array $a$ , so the answer to this query is $0$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted