串\(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;
}