CF1774F2 Magician and Pigs (Hard Version)

这是该问题的困难版本。两种版本的唯一区别在于 $n$ 和 $x$ 的约束条件。只有在两种版本都被解决的情况下，你才能进行 Hack。 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$ 取模。

在第一个样例中，所有操作等价于重复四次：创造一只生命值为 $8$ 的猪，然后将所有存活猪的生命值减少 $3$。很容易发现，最后有两只存活的猪，生命值分别为 $2$ 和 $5$。 由 ChatGPT 4.1 翻译