括弧匹配

代码没怎么看懂，思想就是队列找括弧一对一对的匹配关系，dfs找到不匹配的需要拍扁的一截进行拍扁

在dfs和拍扁的时候都进行递归，从局部考虑整体

#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
inline int in(){
int x = 0;
bool f = 0;
char c = getchar();
while(c > '9' || c < '0'){
if(c == '-') f = 1;
c = getchar();
}
while(c <= '9' && c >= '0'){
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
if(f) return -x;
else return x;
}
const int N = 1e6+10;
char s1[N],s2[N];
int n,top;
int pp1[N],pp2[N],c[N];
inline ll pbcg(int l,int r,int pp[],int fl){
//((···)) => ()()()
//(((···))(...) ((···))) => (()()()()) => (((((()))))) => ()()()()
if(l + 1 == r) return 0;//()
if(pp[r-1] == l+1){//( () (())()
if(fl) {return pbcg(l+1,r-1,pp,1);}
else {return pbcg(l+1,r-1,pp,1)+1;}
}
ll res = 2-fl;//()()()(())
for(int i = l+1;i <= r-1;i = pp[i]+1){
res+=pbcg(i,pp[i],pp,0);
}
return res;
}
inline ll calc(int l,int r){
if(l + 1 == r) return 0;
ll res = 0;
for(int i = l;i <= r;i = pp1[i]+1)
if(pp1[i] == pp2[i]) res += calc(i+1,pp1[i]-1);
else res += pbcg(i,pp1[i],pp1,0);
for(int i = l;i <= r;i = pp2[i]+1)
if(pp1[i] != pp2[i]) res += pbcg(i,pp2[i],pp2,0);
return res;
}
int main(){
//freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n = in();
scanf("%s %s",s1+1,s2+1);
for(int i = 1;i <= n;++i){
if(s1[i] == '(') c[++top] = i;
else pp1[i] = c[top--],pp1[pp1[i]] = i;
}
for(int i = 1;i <= n;++i){
if(s2[i] == '(') c[++top] = i;
else pp2[i] = c[top--],pp2[pp2[i]] = i;
}
// for(int i = 1;i <= n;++i) printf("%d ",pp1[i]);
printf("%lld",calc(1,n));
return 0;
}
/*
8
()(())()
(())(())

8
(((())))
()()()()

8
((()()))
()()()()
*/