Magician and Pigs (Easy Version)
题意翻译
你现在有一个空序列,需要维护如下三个操作:
- $1\ x$:在序列中添加$x$。
- $2\ x$:把序列中每个元素的值减去$x$。
- $3$:重复从第一条到本条操作的前一条的所有操作。包括操作$3$。
当一个数的值小于等于$0$时,它将被移出序列。
请输出最后有多少个数还在序列中。答案对$998244353$取模。
输入格式:
第一行输入一个整数$n(1\leq n \leq 2\times10^5)$,表示操作总数。
接下来的每行由操作名和$x$构成(操作$3$只有操作名)。其中$1\leq x\leq 2\times 10^5$。
题目描述
This is the easy version of the problem. The only difference between the two versions is the constraint on $ n $ and $ x $ . You can make hacks only if both versions of the problem are solved.
Little09 has been interested in magic for a long time, and it's so lucky that he meets a magician! The magician will perform $ n $ operations, each of them is one of the following three:
- $ 1\ x $ : Create a pig with $ x $ Health Points.
- $ 2\ x $ : Reduce the Health Point of all living pigs by $ x $ .
- $ 3 $ : Repeat all previous operations. Formally, assuming that this is the $ i $ -th operation in the operation sequence, perform the first $ i-1 $ operations (including "Repeat" operations involved) in turn.
A pig will die when its Health Point is less than or equal to $ 0 $ .
Little09 wants to know how many living pigs there are after all the operations. Please, print the answer modulo $ 998\,244\,353 $ .
输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1\leq n\leq 2\cdot 10^5 $ ) — the number of operations.
Each of the following $ n $ lines contains an operation given in the form described in the problem statement. It's guaranteed that $ 1\leq x\leq 2\cdot 10^5 $ in operations of the first two types.
输出格式
Print a single integer — the number of living pigs after all the operations, modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
4
1 8
2 3
3
3
输出样例 #1
2
输入样例 #2
6
1 5
1 6
2 2
3
1 4
3
输出样例 #2
5
输入样例 #3
12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3
输出样例 #3
17
说明
In the first example, the operations are equivalent to repeating four times: create a pig with $ 8 $ Health Points and then reduce the Health Points of all living pigs by $ 3 $ . It is easy to find that there are two living pigs in the end with $ 2 $ and $ 5 $ Health Points.