没看懂官方社论，只好自力更生了。
我们很容易知道，对于一段区间，其代价就是多余的括号数（左右括号中多出来的括号数）加上不属于多余括号，但没有匹配的左或右括号数。即左括号总量与右括号总量的最大值减去匹配括号对数。
匹配括号对数很容易线性求出，现在关键就是怎么维护所有区间的左括号总量减去右括号总量。记 \(b\) 左括号在一段前缀中的出现次数，\(c\) 为右括号在一段前缀中的出现次数，那么我们要求的就是 \(\sum_{l=1}^n\sum_{r=l}^n\max(b_r-b_{l-1},c_r-c_{l-1})\)。我一开始以为是扫右端点加线段树维护，但是想了很久很久都没有想出来。后来我 偷偷看了 yyyyxh 的场切代码，发现他用分治做，大受启发， 想到了把这个式子拆成两部分：
为了更方便地维护，我们对式子做一下微调：
所以就转化为了一个偏序问题，可以用分治来维护。具体地，处理区间 \([l,r]\) 时，递归处理 \([l,\text{mid}]\) 和 \([\text{mid}+1,r]\)。把 \([l,\text{mid}]\) 扫一遍作为左端点统计，同时用一个指针维护右半部分第一个或最后一个 \(b-c\) 满足偏序关系的点，然后分别用前缀和和后缀和计算贡献就行了。
时间复杂度为 \(O(n\log n)\)。但是好像跑得和两只 log 的二分做法一样快。
后来看了看 洛谷上的题解，再次感到了自己的弱小。
洛谷的题解前面的思路和我一样。但是在遇到 \(\max(L,R)\) 时，没有把它用分类讨论强制拆开，而是化成了 \(\dfrac{L+R+|L-R|}{2}\) 然后轻松计算，只要一次排序就能爆切。数学方法就是强！
下面是我写的分治做法。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N=2e5+5;
struct Node{
int b,c,d;Node(){b=0;c=0;d=0;}
bool operator<(const Node&O)const{return d<O.d;}
}t[N];char s[N];int n,sta[N];ll ans,sb[N],sc[N];
inline void solve(int l,int r){
if(l==r)return;
int mid=l+r>>1;solve(l,mid);solve(mid+1,r);
sb[r+1]=0;sc[mid]=0;
for(int i=mid+1;i<=r;i++)sc[i]=sc[i-1]+t[i].c;
for(int i=r;i>mid;i--)sb[i]=sb[i+1]+t[i].b;
for(int i=l,p=mid+1;i<=mid;i++){
while(p<=r&&t[p].d<t[i].d)p++;
ans+=sb[p]-(ll)t[i].b*(r-p+1);
ans+=sc[p-1]-(ll)t[i].c*(p-1-mid);
}
inplace_merge(t+l,t+mid+1,t+r+1);
}
inline void ct(){
scanf("%d%s",&n,s+1);ans=0;
for(int i=1,top=0;i<=n;i++){
t[i]=t[i-1];
if(s[i]=='('){
sta[++top]=i;t[i].b++;
}else{
t[i].c++;
if(top)ans-=(ll)sta[top--]*(n-i+1);
}
t[i].d=t[i].b-t[i].c;
}
solve(0,n);
cout<<ans<<'\n';
}
int main(){
int T;cin>>T;while(T--)ct();
return 0;
}
原文地址：http://www.cnblogs.com/hihihi198/p/16882108.html
