@[popossible](/user/579857) 设失配的右括号个数为 $R$，失配的左括号个数为 $L$，要求的是所有区间的 $\sum \max(L,R)$，可以转化为 $\sum \dfrac{L+R+|L-R|}2$。
其中 $\sum |L-R|$ 和原区间内左右括号数量的差的绝对值相等，因为每匹配一对括号两者数量都会相减。把左括号视为 $1$，右括号视为 $-1$，设 $s_i$ 为前 $i$ 个位置的权值之和，那么要求的就是 $\sum\limits_{i=0}^{n-1}\sum\limits_{j=i+1}^n |s_j-s_i|$，把 $s$ 排个序就可以求。
然后是 $\sum L$ 和 $\sum R$，考虑每个左括号的贡献，找出每个左括号 $i$ 匹配的右括号位置 $j$，那么对 $i(j-i)$ 个区间有贡献。右括号类似，只需把序列 reverse 一下再求。
不保证对。
by Lgx_Q @ 2024-03-29 17:00:57
@[Lgx_Q](/user/375953) 是对的捏
但想问问有没有直接拿数据结构优化的方法
by popossible @ 2024-03-29 17:12:07
@[popossible](/user/579857) 感觉不太行
by Lgx_Q @ 2024-03-29 17:22:42
@[Lgx_Q](/user/375953) 只是想问一问而已：）
我再胡一胡
by popossible @ 2024-03-29 17:26:22