CF1239B The World Is Just a Programming Task (Hard Version)

这是该问题的更难版本。在本版本中，$n \le 300\,000$。 Vasya 是一位经验丰富的程序竞赛题目开发者。和所有伟大的人一样，Vasya 也曾遇到过创作瓶颈。为了改善这种状况，Petya 送给了他一个只包含左括号和右括号的字符串。Petya 认为，一个括号字符串的美丽值是它的所有循环移位中，能形成合法括号序列的个数。 为了转移注意力，Vasya 决定选择字符串中的两个位置（可以相同），并交换这两个位置上的字符。Vasya 会恰好执行一次这样的操作。他想知道，通过这样的操作，他最多能让字符串的美丽值达到多少。请你帮帮他。 我们提醒你，括号序列 $s$ 被称为合法的，当且仅当： - $s$ 是空串； - $s$ 等于“($t$)”，其中 $t$ 是合法括号序列； - $s$ 等于 $t_1 t_2$，即 $t_1$ 和 $t_2$ 的连接，其中 $t_1$ 和 $t_2$ 都是合法括号序列。 例如，“(()())”、“()” 是合法的，而 “)(” 和 “())” 不是。 长度为 $n$ 的字符串 $s$ 的循环移位 $k$（$0 \leq k < n$）是指将字符串 $s$ 的最后 $k$ 个字符与前 $n-k$ 个字符拼接而成的新字符串。例如，字符串 “(())()” 循环移位 $2$ 得到 “()(())”。 如果 $i \ne j$，则循环移位 $i$ 和 $j$ 被认为是不同的。

第一行包含一个整数 $n$（$1 \le n \le 300\,000$），表示字符串的长度。 第二行包含一个恰好由 $n$ 个字符组成的字符串，每个字符都是 “(” 或 “)”。

第一行输出一个整数，表示通过交换某两个字符后，字符串能达到的最大美丽值。 第二行输出两个整数 $l$ 和 $r$（$1 \leq l, r \leq n$），表示应交换的两个字符的位置。 如果有多组答案，输出任意一组均可。

在第一个样例中，我们可以交换第 $7$ 个和第 $8$ 个字符，得到字符串 “()()()()()”。该字符串的循环移位 $0, 2, 4, 6, 8$ 都是合法括号序列。 在第二个样例中，交换第 $5$ 个和第 $10$ 个字符后，得到字符串 “)(())()()(()”。该字符串的循环移位 $11, 7, 5, 3$ 都是合法括号序列。 在第三个样例中，任意交换两个括号，合法括号序列的循环移位数都是 $0$。 由 ChatGPT 4.1 翻译