Magician and Pigs (Hard Version) (Codeforces 1774F2)
Tags: Implement, binary search

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

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.

Sample Inputs:
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

Sample Outputs:
2

5

17

Solution (Python):
import sys
input = sys.stdin.buffer.readline
MOD = 998244353
MAXN = 8 * 10 ** 5
MAX_X = 10 ** 9
pow2 = [1]
for i in range(MAXN):
    pow2.append(pow2[-1] * 2 % MOD)
n = int(input())
ops = [list(map(int, input().split())) for i in range(n)]
prefix_decrease = [0] * n
for (i, op) in enumerate(ops):
    prefix_decrease[i] = prefix_decrease[i - 1]
    if prefix_decrease[i] < MAX_X:
        if op[0] == 2:
            prefix_decrease[i] += op[1]
        elif op[0] == 3:
            prefix_decrease[i] *= 2
ans = 0
last_repeat_pos = -1
repeat = []
suffix_decrease = 0
for i in range(n - 1, -1, -1):
    op = ops[i]
    if op[0] == 1:
        x = op[1]
        if prefix_decrease[i]:
            repeat_i = len(repeat)
        else:
            repeat_i = last_repeat_pos + 1
        start_repeat_i = repeat_i
        num_pigs_in_interval_exponent = len(repeat) - repeat_i
        interval_size = 0
        interval_start = x - suffix_decrease
        while repeat_i - 1 >= 0 and interval_start - interval_size >= 2:
            repeat_i -= 1
            interval_size = 2 * (interval_size + repeat[repeat_i]) + prefix_decrease[i]
            interval_start += repeat[repeat_i]
            num_pigs_in_interval_exponent += 1
        while repeat_i != start_repeat_i:
            top_sub_interval_size = (interval_size - prefix_decrease[i]) // 2
            if interval_start - top_sub_interval_size >= 1:
                ans = (ans + pow2[num_pigs_in_interval_exponent - 1]) % MOD
                interval_start -= top_sub_interval_size + prefix_decrease[i]
            interval_size = top_sub_interval_size - repeat[repeat_i]
            interval_start -= repeat[repeat_i]
            num_pigs_in_interval_exponent -= 1
            repeat_i += 1
        if interval_start >= 1:
            ans = (ans + pow2[num_pigs_in_interval_exponent]) % MOD
    elif op[0] == 2:
        x = op[1]
        suffix_decrease += x
        if repeat:
            repeat[-1] += x
            last_repeat_pos = len(repeat) - 1
    else:
        repeat.append(0)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
INV2 = MOD // 2 + 1
P2 = [pow(2, i, MOD) for i in range(31)]
X = 10 ** 9
s2 = 0
s3 = 0
s = []
ipt = []
(n,) = map(int, input().strip().split())
for _ in range(n):
    i = list(map(int, input().strip().split()))
    op = i[0]
    if op == 1:
        ipt.append(i[1])
    elif op == 2:
        s2 += i[1]
        s3 += i[1]
        ipt.append(-i[1])
    elif op == 3 and s3 < X:
        s.append(s3)
        s3 *= 2
        ipt.append(0)
ans = 0
s.append(X + 1)
l = 0
l0 = 0
while l0 < len(s) and s[l0] == 0:
    l0 += 1
tl = l0
p2l0 = pow(2, l0, MOD)
for i in ipt:
    if i == 0:
        if l < l0:
            p2l0 = p2l0 * INV2 % MOD
        l += 1
        tl = max(l, l0)
    elif i < 0:
        s2 += i
    elif i > s2:
        t = 0
        i -= s2
        r = len(s) - 1
        while r > tl and s[r] >= i:
            r -= 1
            if s[r] < i:
                t += P2[r - tl]
                i -= s[r]
        t += P2[r - tl]
        ans = (ans + t % MOD * p2l0) % MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
MOD = 998244353
INV2 = MOD // 2 + 1
P2 = [pow(2, i, MOD) for i in range(31)]
X = 10 ** 9
s2 = 0
s3 = 0
s = []
ipt = []
(n,) = map(int, input().strip().split())
for _ in range(n):
    i = list(map(int, input().strip().split()))
    op = i[0]
    if op == 1:
        ipt.append(i[1])
    elif op == 2:
        s2 += i[1]
        s3 += i[1]
        ipt.append(-i[1])
    elif op == 3 and s3 < X:
        s.append(s3)
        s3 *= 2
        ipt.append(0)
ans = 0
s.append(X + 1)
l = 0
l0 = 0
while l0 < len(s) and s[l0] == 0:
    l0 += 1
tl = l0
p2l0 = pow(2, l0, MOD)
for i in ipt:
    if i == 0:
        if l < l0:
            p2l0 = p2l0 * INV2 % MOD
        l += 1
        tl = max(l, l0)
    elif i < 0:
        s2 += i
    elif i > s2:
        t = 0
        i -= s2
        r = len(s) - 1
        while r > tl and s[r] >= i:
            r -= 1
            if s[r] < i:
                t += P2[r - tl]
                i -= s[r]
        t += P2[r - tl]
        ans = (ans + t % MOD * p2l0) % MOD
print(ans)