大样例#3就过不去了

思路是主流做法

/*
Mon. 2023.5.8
by Sheez
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,ax[N],bx[N];
char a[N],b[N];
bool av[N],bv[N];
stack<int>s;
int mdf(int t[],int l,int r,bool op)
{
    int ret=0;
    if(l+1>=r)return 0;
    // printf("%d %d\n",l,r);
    if(t[l+1]==r-1)
        if(op)ret=mdf(t,l+1,r-1,1);
        else ret=mdf(t,l+1,r-1,1)+1;
    else
    {
        for(int i=l+1;i<r;i=t[i]+1)ret+=mdf(t,i,t[i],0);
        if(op)ret+=1;else ret+=2;
    }
    return ret;
}
int dfs(int l,int r)
{
    if(l+1>=r)return 0;
    int ret=0;
    for(int i=l;i<=r;i=ax[i]+1)
        if(bv[i]&&ax[i]==bx[i])ret+=dfs(i+1,ax[i]-1);
    for(int i=l;i<=r;i=ax[i]+1)
        if(!bv[i]||ax[i]!=bx[i])ret+=mdf(ax,i,ax[i],0);
    for(int i=l;i<=r;i=bx[i]+1)
        if(!av[i]||bx[i]!=ax[i])ret+=mdf(bx,i,bx[i],0);
    return ret;
}
signed main()
{
    scanf("%d",&n);
    scanf("%s%s",a+1,b+1);
    for(int i=1;i<=n;i++)
        if(a[i]=='(')s.push(i);
        else ax[s.top()]=i,s.pop();
    for(int i=1;i<=n;i++)
        if(b[i]=='(')s.push(i);
        else bx[s.top()]=i,s.pop();
    // for(int i=1;i<=n;i++)printf("%d ",ax[i]);puts("");
    // for(int i=1;i<=n;i++)printf("%d ",bx[i]);puts("");
    printf("%d\n",dfs(1,n));
    return 0;
}