← 返回题目列表

Codeforces · 1774/F2

F2. 魔术师与猪(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。两个版本之间的唯一区别是对 $$$n$$$ 和 $$$x$$$ 的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

小09对魔术很感兴趣,很幸运能遇到魔术师!魔术师将执行$$$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$$$。