Magician and Pigs (Hard Version)
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 2700
Tags: binary search, brute force, data structures, implementation

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$$$.

Input format:
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.

Output format:
Print a single integer  — the number of living pigs after all the operations, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
1 8
2 3
3
3

Example output:
2

Example input:
6
1 5
1 6
2 2
3
1 4
3

Example output:
5

Editorial:
F1
Let $$$X=\max x$$$.
Think about what "Repeat" is doing. Assuming the total damage is $$$x$$$ ($$$x$$$ is easy to calculate because it will be multiplied by $$$2$$$ after each 'Repeat' and be added after each "Attack"). After repeating, each pig with a current HP of $$$w$$$ ($$$w > x$$$) will clone a pig with a HP of $$$w-x$$$.
Why? "Repeat" will do what you just did again, so each original pig will certainly create a pig the same as it, and it will be attacked by $$$x$$$, so it can be considered that a pig with $$$w-x$$$ HP has been cloned.
Next, the problem is to maintain a multiset $$$S$$$, which supports: adding a number, subtracting $$$x$$$ for all numbers, and inserting each number after subtracting $$$x$$$. Find the number of elements in the final multiset.
$$$x$$$ in "Repeat" after the first "Attack" will multiply by $$$2$$$ every time, so it will exceed $$$X$$$ in $$$O(\log X)$$$ times. We can maintain $$$S$$$ violently. Every time we "Repeat", we take out all the numbers, then subtract and insert them again. If you use map to maintain it, the time complexity is $$$O((n+X)\log ^2X)$$$. It can pass F1.
————
F2
For F1, there is another way. Consider every pig. When "Repeat", it will clone, and when "Attack", all its clones will be attacked together. Therefore, considering all the operations behind each pig, you can choose to reduce $$$x$$$ (the current total damage) or not when "Repeat", and you must choose to reduce $$$x$$$ when "Attack". Any final choice will become a pig (alive or not).
We just need to calculate how many "Repeat" choices can make a living pig. For "Repeat" of $$$x=0$$$, there is no difference between the two choices. For the "Repeat" of $$$x\geq 2\times 10^5$$$, it is obvious that you can only choose not to reduce $$$x$$$. Except for the above parts, there are only $$$O(\log x)$$$ choices. You can just find a subset or use knapsack to solve it. It can also pass F1 and the time complexity is $$$O((n+X)\log X)$$$.
The bottleneck of using this method to do F2 lies in the backpack. The problem is that we need to find the sum $$$<x$$$ of how many subsets of a set whose size is $$$O(\log X)$$$.
Observation: if you sort the set, each element is greater than the sum of all elements smaller than it. We can use observation to solve the problem. Consider each element from large to small. Suppose you now need to find elements and subsets of $$$<x$$$. If the current element $$$\ge x$$$, it must not be selected; If the current element $$$<x$$$, if it is not selected, the following elements can be selected at will (the sum of all the following elements is less than it). It can be recursive. So we can find the number of subsets whose sum $$$<x$$$ within $$$O(\log X)$$$.
The time complexity is $$$O(n\log X)$$$.