CF1264D2 Beautiful Bracket Sequence (hard version)

这是本题的困难版本。唯一的区别在于输入字符串的长度 $n$ 的限制。在本版本中，$1 \leq n \leq 10^6$。 我们定义一个合法括号序列及其深度如下： - 空字符串是一个合法括号序列，深度为 $0$。 - 如果 $s$ 是一个深度为 $d$ 的合法括号序列，那么 $(s)$ 是一个深度为 $d+1$ 的合法括号序列。 - 如果 $s$ 和 $t$ 都是合法括号序列，那么它们的连接 $st$ 也是合法括号序列，其深度为 $s$ 和 $t$ 的最大深度。 对于一个（不一定合法的）括号序列 $s$，我们定义其深度为：通过删除 $s$ 中的某些字符（可以为零个）得到的所有合法括号序列中，最大深度的值。例如，括号序列 $s = $ "())(())" 的深度为 $2$，因为删除第三个字符后可以得到合法括号序列 "()(())"，其深度为 $2$。 给定一个只包含 '('、')' 和 '?' 的字符串 $a$。考虑将 $a$ 中所有的 '?' 替换为 '(' 或 ')' 得到的所有（不一定合法的）括号序列。请计算所有这些括号序列的深度之和。由于答案可能很大，请输出对 $998244353$ 取模的结果。 本题只有在简单版和困难版都通过后才能 Hack。

一行，包含一个只由 '('、')' 和 '?' 组成的非空字符串。字符串长度不超过 $10^6$。

输出一个整数，表示所有括号序列深度之和对 $998244353$ 取模的结果。

在第一个测试样例中，将所有 '?' 替换后可以得到 $4$ 个括号序列： - "(("，深度为 $0$； - "))"，深度为 $0$； - ")("，深度为 $0$； - "()"，深度为 $1$。 因此，答案为 $1 = 0 + 0 + 0 + 1$。 在第二个测试样例中，将所有 '?' 替换后可以得到 $4$ 个括号序列： - "(((())"，深度为 $2$； - "()()))"，深度为 $2$； - "((()))"，深度为 $3$； - "()(())"，深度为 $2$。 因此，答案为 $9 = 2 + 2 + 3 + 2$。 由 ChatGPT 4.1 翻译