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$ 取模的结果。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

??

输出 #1

1

输入输出样例 #2

输入 #2

(?(?))

输出 #2

9

说明/提示

在第一个测试样例中，将所有 '?' 替换后可以得到 $4$ 个括号序列：

• "(("，深度为 $0$；
• "))"，深度为 $0$；
• ")("，深度为 $0$；
• "()"，深度为 $1$。

因此，答案为 $1 = 0 + 0 + 0 + 1$。

在第二个测试样例中，将所有 '?' 替换后可以得到 $4$ 个括号序列：

• "(((())"，深度为 $2$；
• "()()))"，深度为 $2$；
• "((()))"，深度为 $3$；
• "()(())"，深度为 $2$。

因此，答案为 $9 = 2 + 2 + 3 + 2$。

由 ChatGPT 4.1 翻译