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();
	}	
	
}