括号匹配（二位数点）

串\(S\)有左右括号和通配符\(?\)，问\(S\)有多少子串可以成为合法括号串。

其中，\(|S|\le10^6\)

思考：一个区间如何合法？

1，该区间长度为偶数

2，令 \((\) 和 \(?\) 为 \(1\) ， \()\) 为 \(-1\) ， 该区间的前缀和里没有负数

3，令 \()\) 和 \(?\) 为 \(1\) ， \((\) 为 \(-1\) ， 该区间的后缀和里没有负数

考虑记下面两个数组：

记\(ne_i\)表示：令 \((\) 和 \(?\) 为 \(1\) ， \()\) 为 \(-1\) ， \([i,ne_i]\)的前缀和里没有负数，若\(ne_i\)有多种可能性，则\(ne_i\)为最大的那个数

记\(pre_i\)表示：令 \()\) 和 \(?\) 为 \(1\) ， \((\) 为 \(-1\) ， \([pre_i,i]\)的后缀和里没有负数，若\(pre_i\)有多种可能性，则\(pre_i\)为最小的那个数

这两个可以使用单调栈处理。

那我们可以将问题转换成：

枚举每个\(i\in [1,|S|]\)，求有多少个\(j\)满足\(j\in [i,ne_i],pre_j\le i\)

把它转换成二位数点：

考虑对于每个构建直角坐标系，在坐标系中加入点\((l,ne_l),(l,l-1)\)，并且对于每个点考虑有多少个\((pre_r,r)\)在它的左下角。答案记作\(ans_{(l,ne_l)}\)，则对于每个\(i\)，它的贡献为\(ans_{(l,ne_l)}-ans_{(l,l-1)}\)

注意，要开奇偶两个数组，因为\(2|(r-l+1)\)

考虑树状数组优化，时间复杂度\(O(|S| \log |S|)\)

#include<bits/stdc++.h>
#define lowbit(pos) pos&(-pos)
using namespace std;

const int maxn=1e6+5;

int n,p[maxn],q[maxn],sum[maxn],st[maxn],tot=0,cnt=0;
char s[maxn];
long long ans=0;
struct node {
	int r,p,k,op;
}t[maxn<<1];
bool cmp(node a,node b) {
	return a.p<b.p;
}
int tr[2][maxn];
void add(int pos,int k,int op) {
	for(;pos<=n;pos+=lowbit(pos))
		tr[op][pos]+=k;
}
int query(int pos,int op) {
	int ret=0;
	for(;pos;pos-=lowbit(pos))
		ret+=tr[op][pos];
	return ret;
}

int main() {
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) {
		sum[i]=sum[i-1];
		if(s[i]!=')') sum[i]++;
		else sum[i]--;
	}
	for(int i=n;i>=1;i--) {
		st[++tot]=i;
		while(tot&&sum[st[tot]]>=sum[i-1]) tot--;
		if(tot) p[i]=st[tot]-1;
		else p[i]=n;
	}
	tot=0;
	for(int i=n;i>=1;i--) {
		sum[i]=sum[i+1];
		if(s[i]!='(') sum[i]++;
		else sum[i]--;
	}
	for(int i=1;i<=n;i++) {
		st[++tot]=i;
		while(tot&&sum[st[tot]]>=sum[i+1]) tot--;
		if(tot) q[i]=st[tot]+1;
		else q[i]=1;
	}
	for(int i=1;i<=n;i++)
		if(i<=p[i]) {
			t[++cnt]={i,p[i],1,i&1};
			if(i>1) t[++cnt]={i,i-1,-1,i&1};
		}
	sort(t+1,t+1+cnt,cmp);
	for(int i=1,j=1;i<=n&&j<=cnt;i++) {
		if(q[i]<=i) add(q[i],1,i&1);
		while(j<=cnt&&t[j].p==i) {
			ans+=t[j].k*query(t[j].r,1-t[j].op);
			j++;
		}
	}
	printf("%lld",ans);
	return 0;
}