Preface
甜橙好闪，拜谢甜橙。来一发验题人题解。
其实这题是出题人看错题后对着 CF1750E 出的，头图里的「只有一笔」指的是 oi 生只有这一道题。
Solution
直接考虑线性做法。
我们需要计数两个问题：
-
- 每个区间需要增加多少个括号：
对于一个有 \(x\) 个 \(\texttt (\)，\(y\) 个 \(\texttt )\) 的区间，我们 至少 需要增加 \(\lvert x - y \rvert\) 个括号才能让它匹配（下面会证该至少可以取到）。
如果我们以 \(\texttt (\) 为 \(-1\)，\(\texttt )\) 为 \(1\) 做前缀和序列 \(c_0 \dots c_n\)，那么容易得到 \(y - x\) 就是 \(c_r - c_{l - 1}\)。我们要求所有 \(1 \leq l \leq r \leq n\) 的相减绝对值贡献，其实就是求所有 \(\color{red}0 \color{normal}\leq l - 1 \color{red}\lt \color{normal} r \leq n\) 的相减绝对值贡献。
排序后，我们可以 \(\mathcal O(1)\) 算出每个 \(c_i\) 在式子里要加多少次，要减多少次，所以可以 \(\mathcal O(n)\) 算出。注意到值域是 \(-n \sim n\) 的，所以桶排即可线性。
-
- 每个区间需不需要位移。
通过 Rayne 引理的形式，我们可以证明每个括号区间任意旋转一次（显然旋转任意次可以合并为一次）肯定能够匹配。更具体地，只有至少一个左括号失配和至少一个右括号失配，才需要旋转，证明显然：
- 因为你在上文的最优情况下只会加同一种括号，故而只能最多改变一种括号的失配状况；
- 位移一次后至少多了一对匹配的括号，比增加操作更优。
但是你发现不会计数需要位移的区间个数（其实大概也是能做的，不过我懒得想。）因此，正难则反，考虑计数不需要位移的区间个数，这等于 没有右括号失配的区间个数 加上 没有左括号失配的区间个数 再减去 完全匹配的区间个数，因为完全匹配的区间会被算两遍。
作为熟练的括号序列做题人，我们考虑 dp。设 \(f_r\) 表示对于所有 \(1 \leq l \leq r\)，满足 \([l, r]\) 没有右括号失配的区间个数。转移有：
- 若 \(S_r = \texttt (\)，则 \(f_r = f_{r - 1} + 1\)；
- 否则 \(f_r = f_{lst_{c_r}} + 1\)，其中 \(lst_x\) 表示上一个 \(u\) 满足 \(c_u = x\)，可以在扫一遍进行 dp 的同时用桶维护。
可以结合图示更好理解这一 dp 过程的正确性。
对于没有左括号失配，我们同理设计状态：
设 \(g_l\) 表示对于所有 \(l \leq r \leq n\)，满足 \([l, r]\) 没有左括号失配的区间个数。转移有：
- 若 \(S_l = \texttt )\)，则 \(g_l = g_{l + 1} + 1\)；
- 否则 \(g_l = g_{lst_{c_{l - 1}} + 1} + 1\)，其中 \(lst_x\) 表示下一个 \(u\) 满足 \(c_u = x\)，同样可以在扫一遍进行 dp 的同时用桶维护。
以上可以自己画图理解。至于求完全匹配的区间个数，同样可以 dp 处理，留作习题。
总时间复杂度 \(\mathcal O(n)\)，绝世好题。
Code
抽象程度顶级，我都怀疑这是不是我写的代码了。
#include <bits/stdc++.h>
#define MAXN 4000005
int c[MAXN], cnt[MAXN], lst[MAXN], f[MAXN], g[MAXN];
void solve() {
int N; std::string S; std::cin >> N >> S; long long ans = 1ll * N * (N + 1) / 2;
++cnt[c[0] = N]; for (int i = 1; i <= N; ++i) ++cnt[c[i] = c[i - 1] + (S[i - 1] == '(' ? -1 : 1)];
for (int i = 0, q = 0, p = N << 1; i <= p; ++i) { while (cnt[i]--) ans += (2ll * (q++) - N) * i; cnt[i] = 0; }
memset(f, 0, sizeof(int) * (N + 5)), memset(g, 0, sizeof(int) * (N + 5)), memset(lst, 0, sizeof(int) * (N + 2 << 1));
for (int r = 1; r <= N; ++r) ans += (g[r] = ((lst[c[r]] || c[r] == N) && S[r - 1] == ')' ? g[lst[c[r]]] + 1 : 0)) - (f[r] = (S[r - 1] == '(' ? f[r - 1] + 1 : (lst[c[r]] || c[r] == N) ? f[lst[c[r]]] + 1 : 0)), lst[c[r]] = r;
memset(f, 0, sizeof(int) * (N + 5)), memset(lst, 0, sizeof(int) * (N + 2 << 1));
for (int l = N; l; --l) ans -= (f[l] = (S[l - 1] == ')' ? f[l + 1] + 1 : lst[c[l - 1]] ? f[lst[c[l - 1]] + 1] + 1 : 0)), lst[c[l]] = l; std::cout << ans << '\n';
}
int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr), std::cout.tie(nullptr); int T; std::cin >> T; while (T--) solve(); return 0; }