310037: CF1774F2. Magician and Pigs (Hard Version)
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Magician and Pigs (Hard Version)
题意翻译
你现在有一个空序列，需要维护如下三个操作： - $1\ x$：在序列中添加 $x$。 - $2\ x$：把序列中每个元素的值减去 $x$。 - $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。 当一个数的值小于等于 $0$ 时，它将被移出序列。 请输出最后有多少个数还在序列中。答案对$998244353$ 取模。 输入格式： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。 接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。题目描述
This is the hard 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 8\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 10^9 $ 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.Input
题意翻译
你现在有一个空序列，需要维护如下三个操作： - $1\ x$：在序列中添加 $x$。 - $2\ x$：把序列中每个元素的值减去 $x$。 - $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。 当一个数的值小于等于 $0$ 时，它将被移出序列。 请输出最后有多少个数还在序列中。答案对$998244353$ 取模。 输入格式： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。 接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。Output
**题意翻译**
你现在有一个空序列，需要维护如下三个操作：
- $1\ x$：在序列中添加 $x$。
- $2\ x$：把序列中每个元素的值减去 $x$。
- $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。
当一个数的值小于等于 $0$ 时，它将被移出序列。
请输出最后有多少个数还在序列中。答案对$998244353$ 取模。
**输入格式**： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。
接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。
**题目描述**
这是问题的困难版本。两个版本之间的唯一区别是 $ n $ 和 $ x $ 的约束。只有当两个版本的问题都解决时，你才能进行 hacks。
Little09 很久以来一直对魔术感兴趣，幸运的是他遇到了一位魔术师！魔术师将执行 $ n $ 个操作，每个操作都是以下三种之一：
- $ 1\ x $：创建一个具有 $ x $ 生命值的猪。
- $ 2\ x $：将所有活着的猪的生命值减去 $ x $。
- $ 3 $：重复所有之前的操作。形式上，假设这是操作序列中的第 $ i $ 个操作，依次执行前 $ i-1 $ 个操作（包括涉及的“重复”操作）。
当猪的生命值小于或等于 $ 0 $ 时，猪将死亡。
Little09 想知道所有操作结束后有多少只活着的猪。请输出答案，模 $ 998\,244\,353 $。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ n $ ($ 1\leq n\leq 8\cdot 10^5 $) — 操作的数量。
接下来的 $ n $ 行包含按问题描述的形式给出的操作。保证在第一和第二种操作中 $ 1\leq x\leq 10^9 $。
**输出格式**
打印一个整数 — 所有操作结束后活着的猪的数量，模 $ 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
```
**说明**
在第一个例子中，操作等同于重复四次：创建一个具有 $ 8 $ 生命值的猪，然后减去所有活着的猪的生命值 $ 3 $。很容易找到最后有两只活着的猪，生命值为 $ 2 $ 和 $ 5 $。**题意翻译** 你现在有一个空序列，需要维护如下三个操作： - $1\ x$：在序列中添加 $x$。 - $2\ x$：把序列中每个元素的值减去 $x$。 - $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。 当一个数的值小于等于 $0$ 时，它将被移出序列。 请输出最后有多少个数还在序列中。答案对$998244353$ 取模。 **输入格式**： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。 接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。 **题目描述** 这是问题的困难版本。两个版本之间的唯一区别是 $ n $ 和 $ x $ 的约束。只有当两个版本的问题都解决时，你才能进行 hacks。 Little09 很久以来一直对魔术感兴趣，幸运的是他遇到了一位魔术师！魔术师将执行 $ n $ 个操作，每个操作都是以下三种之一： - $ 1\ x $：创建一个具有 $ x $ 生命值的猪。 - $ 2\ x $：将所有活着的猪的生命值减去 $ x $。 - $ 3 $：重复所有之前的操作。形式上，假设这是操作序列中的第 $ i $ 个操作，依次执行前 $ i-1 $ 个操作（包括涉及的“重复”操作）。 当猪的生命值小于或等于 $ 0 $ 时，猪将死亡。 Little09 想知道所有操作结束后有多少只活着的猪。请输出答案，模 $ 998\,244\,353 $。 **输入输出格式** **输入格式** 第一行包含一个整数 $ n $ ($ 1\leq n\leq 8\cdot 10^5 $) — 操作的数量。 接下来的 $ n $ 行包含按问题描述的形式给出的操作。保证在第一和第二种操作中 $ 1\leq x\leq 10^9 $。 **输出格式** 打印一个整数 — 所有操作结束后活着的猪的数量，模 $ 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 ``` **说明** 在第一个例子中，操作等同于重复四次：创建一个具有 $ 8 $ 生命值的猪，然后减去所有活着的猪的生命值 $ 3 $。很容易找到最后有两只活着的猪，生命值为 $ 2 $ 和 $ 5 $。
你现在有一个空序列，需要维护如下三个操作：
- $1\ x$：在序列中添加 $x$。
- $2\ x$：把序列中每个元素的值减去 $x$。
- $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。
当一个数的值小于等于 $0$ 时，它将被移出序列。
请输出最后有多少个数还在序列中。答案对$998244353$ 取模。
**输入格式**： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。
接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。
**题目描述**
这是问题的困难版本。两个版本之间的唯一区别是 $ n $ 和 $ x $ 的约束。只有当两个版本的问题都解决时，你才能进行 hacks。
Little09 很久以来一直对魔术感兴趣，幸运的是他遇到了一位魔术师！魔术师将执行 $ n $ 个操作，每个操作都是以下三种之一：
- $ 1\ x $：创建一个具有 $ x $ 生命值的猪。
- $ 2\ x $：将所有活着的猪的生命值减去 $ x $。
- $ 3 $：重复所有之前的操作。形式上，假设这是操作序列中的第 $ i $ 个操作，依次执行前 $ i-1 $ 个操作（包括涉及的“重复”操作）。
当猪的生命值小于或等于 $ 0 $ 时，猪将死亡。
Little09 想知道所有操作结束后有多少只活着的猪。请输出答案，模 $ 998\,244\,353 $。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ n $ ($ 1\leq n\leq 8\cdot 10^5 $) — 操作的数量。
接下来的 $ n $ 行包含按问题描述的形式给出的操作。保证在第一和第二种操作中 $ 1\leq x\leq 10^9 $。
**输出格式**
打印一个整数 — 所有操作结束后活着的猪的数量，模 $ 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
```
**说明**
在第一个例子中，操作等同于重复四次：创建一个具有 $ 8 $ 生命值的猪，然后减去所有活着的猪的生命值 $ 3 $。很容易找到最后有两只活着的猪，生命值为 $ 2 $ 和 $ 5 $。**题意翻译** 你现在有一个空序列，需要维护如下三个操作： - $1\ x$：在序列中添加 $x$。 - $2\ x$：把序列中每个元素的值减去 $x$。 - $3$：重复从第一条到本条操作的前一条的所有操作。包括操作 $3$。 当一个数的值小于等于 $0$ 时，它将被移出序列。 请输出最后有多少个数还在序列中。答案对$998244353$ 取模。 **输入格式**： 第一行输入一个整数 $n(1\leq n \leq 8\times10^5)$，表示操作总数。 接下来的每行由操作名和 $x$ 构成（操作 $3$ 只有操作名）。其中 $1\leq x\leq 10^9$。 **题目描述** 这是问题的困难版本。两个版本之间的唯一区别是 $ n $ 和 $ x $ 的约束。只有当两个版本的问题都解决时，你才能进行 hacks。 Little09 很久以来一直对魔术感兴趣，幸运的是他遇到了一位魔术师！魔术师将执行 $ n $ 个操作，每个操作都是以下三种之一： - $ 1\ x $：创建一个具有 $ x $ 生命值的猪。 - $ 2\ x $：将所有活着的猪的生命值减去 $ x $。 - $ 3 $：重复所有之前的操作。形式上，假设这是操作序列中的第 $ i $ 个操作，依次执行前 $ i-1 $ 个操作（包括涉及的“重复”操作）。 当猪的生命值小于或等于 $ 0 $ 时，猪将死亡。 Little09 想知道所有操作结束后有多少只活着的猪。请输出答案，模 $ 998\,244\,353 $。 **输入输出格式** **输入格式** 第一行包含一个整数 $ n $ ($ 1\leq n\leq 8\cdot 10^5 $) — 操作的数量。 接下来的 $ n $ 行包含按问题描述的形式给出的操作。保证在第一和第二种操作中 $ 1\leq x\leq 10^9 $。 **输出格式** 打印一个整数 — 所有操作结束后活着的猪的数量，模 $ 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 ``` **说明** 在第一个例子中，操作等同于重复四次：创建一个具有 $ 8 $ 生命值的猪，然后减去所有活着的猪的生命值 $ 3 $。很容易找到最后有两只活着的猪，生命值为 $ 2 $ 和 $ 5 $。