题解：CF2063F2 Counting Is Not Fun (Hard Version)

· · 题解

提供一个疑似是本题最简单的做法，并且我们爆标了。practical 的复杂度是 \mathcal O(n\alpha(n))，使用线性树上并查集我们可以做到线性。

感谢 @StayAlone 提供的细节帮助，感谢 @AfterFullStop 指出本做法可以做到线性。

回顾 F1 的做法：

我们对已知的匹配括号建立括号串分治树。具体来说，树上每个节点都是一对匹配括号 (u,R_u)，我们按照它们的包含和不交关系建立成树。

有了树结构，答案是容易表示的。我们维护每个节点下没有被儿子匹配管辖的空位的长度 l_u，即 l_u=R_u-u-1-(\sum\limits_{v\in \operatorname{son}(u)} R_v-v+1)。它产生的贡献就是这一长度的合法括号串的数量，也就是一个卡特兰数 C_{\frac{l_u}{2}}。

答案把所有节点的贡献乘起来就好。

延续 F1 的做法。我们尝试维护分治树，考虑每次加入一个节点产生的影响。因为加入节点需要操作子树，这不太方便，我们考虑时光倒流。

时光倒流之后，每次我们只需删除一个节点，把它的儿子挂到它的父亲上。贡献上会产生的影响只有删去它的 l 的贡献，再改变它父亲的 l 的贡献，结构上也只会影响此处的父亲关系。

我们直接用逆元撤销掉原来的贡献，再把新的贡献加上去，同时维护 l。

考虑剩下的问题是我们还需要也仅需要维护分治树上的父亲关系，需要支持删除一个节点。类似可并堆的处理办法，考虑我们没必要真实删除这个节点，把它重定向到它的父亲即可。用一个并查集就可以简单维护好。

实现上，因为分治树上所有节点的端点都互不相同，所以我们可以从端点映射节点规避 map；卡特兰数及其逆元可以用线性阶乘逆元、线性逆元 \mathcal O(1) 得到。于是时间复杂度瓶颈是并查集。

树上并查集直接写可以做到 \mathcal O(n\alpha(n))，使用线性树上并查集就可以把整个东西打成线性。

下面是一个懒得写按秩合并所以带 \log 的代码：

int tc;
int n;
ll fac[N],ifac[N],inv[N];
ll qpow(ll b,int p){
    if(!p) return 1;
    ll d=qpow(b,p>>1);
    if(p&1) return d*d%mod*b%mod;
    else return d*d%mod;
}
void init(int n=1.2e6){
    fac[0]=1;
    fr1(i,1,n) fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    fr2(i,n-1,0) ifac[i]=ifac[i+1]*(i+1)%mod;
    fr1(i,1,n) inv[i]=ifac[i]*fac[i-1]%mod;
}
ll Ca(int n){
    return fac[n]*ifac[n>>1]%mod*ifac[n>>1]%mod*inv[(n>>1)+1]%mod;
}
ll iCa(int n){
    return ifac[n]*fac[n>>1]%mod*fac[n>>1]%mod*((n>>1)+1)%mod;
}
int mat[N];
vector <int> op;
vector <int> res;
int fa[N],dirf[N];
int len[N];
int node[N];
int tot;
int find(int x){
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void divide(int f,int l,int r){
    tot++;
    node[l]=tot;
    len[tot]=0,dirf[tot]=f,fa[tot]=tot;
    int cnt=0;
    fr1(i,l+1,r-1){
        divide(node[l],i,mat[i]);
        i=mat[i];
    }
}
void solve(){
    tot=0;
    op.clear(),res.clear();
    cin>>n;
    fr1(i,1,(n<<1)) mat[i]=0;
    fr1(i,1,n){
        int u,v;
        cin>>u>>v;
        mat[u]=v;
        op.pb(u);
    }
    divide(0,0,(n<<1)+1);
    ll ans=1;
    fr2(i,n-1,0){
        res.pb(ans);
        int id=op[i];
        int u=node[id];
        int f=find(dirf[u]);
        (ans*=iCa(len[u]))%=mod;
        (ans*=iCa(len[f]))%=mod;
        len[f]+=len[u]+2;
        (ans*=Ca(len[f]))%=mod;
        fa[u]=f;
    }
    res.pb(ans);
    while(!res.empty()){
        cout<<res.back()<<" ";
        res.pop_back();
    }
    cout<<'\n';
}