D-二分
最近做了一个CFround166的d题然后发现我并不会二分（虽然标答并不是二分）。故来写一下。
题目：https://codeforces.com/contest/1976/problem/D
首先观察到几个显而易见的性质：
1.若要翻转[l,r],[l,r]中的(和)数量相等
2.为了能和前面匹配上，翻转后[l,r]中未匹配右括号的（最大)数量要等于[1,l-1]中未匹配左括号的数量。
好的到这里我就不会了。但是如果考虑左括号比右括号多的数量并且把每个位置的值设为{a_i}，那么就可以实现这两个性质的量化(这一步真的想不到，感觉数学思维要加强，其实有点像一个入栈出栈的操作吧。
1.\({a_{l-1}==a_r}\)
2.\({a_{l-1}>=a_i-a{l-1}}\)(最大未匹配的右括号不能多于未匹配的左括号）,可变形简化为\(a_{l-1}*2>=a_i\)
那么我们想如果固定l-1，r的取值一定是l-1右边连续的一个范围，因为有一个不满足的显然右边所有点都不满足。
我：这个不能二分，因为二分要在有序的序列上进行。 佬：答案具有单调性就可以二分。
然后我想了一下用线段树维护mx的话确实是可以二分的。所以写完了。
#include<bits/stdc++.h>
using namespace std;
#define ls(x) (x<<1)
#define rs(x) ((x<<1)+1)
#define mid ((l+r)>>1)
#define int long long
const int mod=1e9+7;
const int maxn=2e5+10;
int sta[maxn],pos[maxn];
int t[maxn*4];
vector<int>E[maxn];
void build(int x,int l,int r){
if(l==r){
t[x]=sta[l];return;
}
build(ls(x),l,mid);
build(rs(x),mid+1,r);
t[x]=max(t[ls(x)],t[rs(x)]);
}
int que(int x,int ql,int qr,int l,int r){
if(l>=ql&&r<=qr){
return t[x];
}
int res=0;
if(mid>=ql)res=que(ls(x),ql,qr,l,mid);
if(mid<qr)res=max(res,que(rs(x),ql,qr,mid+1,r));
return res;
}
void solve(){
string s;cin>>s;
for(int i=0;i<=s.size();i++)E[i].clear(),pos[i]=0;
for(int i=0,w=0;i<s.size();i++){
if(s[i]=='(')w++;
else w--;
sta[i+1]=w;
E[w].push_back(i+1);
pos[i+1]=E[w].size()-1;
}
int n=s.size(),ans=0;
build(1,1,n);
//cout<<1;
for(int i=1;i<s.size();i++){
int l=i+1,r=n,mid1=(l+r+1)>>1;
while(l<r){
if(que(1,l,mid1,1,n)<=sta[i]*2){
l=mid1;
}
else r=mid1-1;
mid1=(l+r+1)>>1;
}
int w=sta[i];
l=0,r=E[w].size()-1;
int mid2=(l+r+1)>>1;
while(l<r){
if(E[w][mid2]<=mid1)l=mid2;
else r=mid2-1;
mid2=(l+r+1)>>1;
}
ans+=mid2-pos[i];
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int tt;cin>>tt;while(tt--){
solve();
}
}