codeforces#P1774F2. Magician and Pigs (Hard Version)
Magician and Pigs (Hard Version)
Description
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$.
Input
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
Print a single integer — the number of living pigs after all the operations, modulo $998\,244\,353$.
4
1 8
2 3
3
3
6
1 5
1 6
2 2
3
1 4
3
12
2 1
1 15
1 9
3
1 12
2 2
1 13
3
2 1
1 9
1 8
3
2
5
17
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.