题解 P9201 「GMOI R2-T4」电子木鱼

· · 题解

LCT 维护基环树森林的题似乎不常见，写篇题解记录一下。

题目大意

有 n 个元素 \operatorname{pair}(d,S)，其中 d\in[1,m]，S\subseteq\{1,2,\cdots,m\}。

不断进行以下操作：

问最少在末尾添加几个元素可以使操作无限进行。

对每个 [1,n] 的子区间 [l,r] 求出答案 f(l,r)，并输出 \sum_{[l,r]}f(l,r)\cdot 2^l 对 10^9+7 取模的结果。

1\le n\le 10^5$，$1\le m\le 17

先考虑单个询问。

状压集合，然后操作变成每个 S 异或上 2^{d_*}。

由于是全局异或，显然只需要关心目前异或的总量。

并且，对一个总异或和为 p 的局面，取出的元素是确定的（即编号最小的 S=p 的元素），新局面是唯一的，如果取不出来那么操作结束，这是我们所需要避免的。因此可以对局面之间的转移建图（点集为 \{0,1,\cdots 2^m-1\}），用有向边刻画关系，形成一个内向树或内向基环树森林。

思考加一个元素的直观感受，显然新加元素的 S 不会与之前的某个 S 相同（因为永远不会用到它），因此新加一个元素可以看做选择一个无出边的点，加一条出边，且指向的点和它差恰好一个二进制位。

而操作能无限进行，就相当于从 0 出发能到一个环。

现在可以考虑求解答案了：

这样，枚举 l，然后从小到大枚举 r，维护一个并查集即可。

int Find(int x){ return fa[x]==x?x:fa[x]=Find(fa[x]); }
void Union(int x, int y){
    x=Find(x),y=Find(y);
    if (x!=y) fa[x]=y,siz[y]+=siz[x],cnt[y]+=cnt[x],S[y]|=S[x];
    cnt[y]--;
    flag|=cnt[y]==0 && S[y];
}
int main(){
    scanf("%d%d",&n,&m); pw[0]=1;
    for (int i=1; i<=n+1; i++) pw[i]=pw[i-1]*2%mod;
    for (int i=1; i<=n; i++){
        scanf("%d%s",&d[i],s);
        for (int j=0; j<m; j++) sta[i]|=(s[j]-'0')<<j;
    }
    for (int i=1; i<=n; i++){
        flag=0;
        for (int j=0; j<(1<<m); j++) vis[j]=0,fa[j]=j,cnt[j]=siz[j]=1,S[j]=__builtin_popcount(j)==1;
        for (int j=i; j<=n; j++){
            if (!vis[sta[j]]) Union(sta[j]^(1<<(d[j]-1)),sta[j]);
            int u=Find(0); vis[sta[j]]=1;
            if (siz[u]==1) ans=(ans+(flag?pw[i]:pw[i+1]))%mod;
            else if (cnt[u]) ans=(ans+pw[i])%mod;
            else break;
        }
    }
    printf("%d\n",ans);
}

然后考虑正解。

那么我只需要分别求出从 $l$ 开始加边，$0$ 以及每个 $\operatorname{popcnt}=1$ 的节点在某个内向基环树的**最小右端点**。 设第一部分为 $T_1$，第二部分的 $\min$ 为 $T_2$，那么： - $r\in[l,T_2-1]$，同时 $[l,r]$ 内不存在与 $0$ 相关的连边，这部分贡献 $1$。 - $r\in [l,T_1-1]$ 这部分也贡献 $1$。 （注意我把上面答案为 $2$ 的情况拆成两部分贡献了） 于是考虑怎么维护右端点，每个点记录一个点权表示它在序列中的下标，那么相当于从某个起点出发走到环，经过点权的 $\max$（如果不会走到环那么记为 $n+1$）。 于是变成了一个类似加边，删边，查到根路径点权 $\max$ 的问题，唯一区别在于变成了基环树，我们强行改造 LCT 使它能维护这个问题。 对于每个弱连通块维护一个**有根树**结构： - 若它为内向树，以无出边的那个点为根。 - 若它为内向基环树，以环上任意一个点为根，并记录其出边指向的节点，称这条边为**附加边**。 再具体讨论一下加删边的细节： ##### 删边：删除 $u$ 的出边 - $u$ 为所在弱连通块的根，那么直接把附加边去掉即可。 - $u$ 不为根，如果弱连通块为内向树则直接断掉，如果是内向基环树，要分是否为环边进行讨论。 - 首先确定是否为环边，记附加边的另一端为 $x$，那么相当于判定 $u$ 是否在 $x$ 到根路径上，这个可以通过 `access(x),splay(x)` 打通 $x$ 到根的路径，然后从 $u$ 开始跳到所在 splay 的根，判是否与 $x$ 相同即可。 - 如果是环边，那么断掉它，连上附加边，同时把**树根定为 $u$**。 - 如果不是环边，那么正常断边。 ##### 加边：加上 $u$ 的出边 $u\rightarrow t

注意 Link，Cut 均有可能改变树根，因此在做完 LCT 操作后都要注意恢复正确的树根。.

最后一部分是查询：

时间复杂度为 O(nm\log n)。

代码有相当的细节，而且考场代码相当丑陋，省略了标准 LCT 操作。

inline void upd(int u, int x, int i){
    if (To[u]){
        if ((u==1 || To[u]==1) && w[u]) S.erase(w[u]); //w[u] 为点权，To[u] 为 u 的出边
        int rt=Findroot(u);
        if (u==rt) E[u]=0; //E 为附加边指向的另一个节点
        else if (!E[rt]){
            int tmp=Findroot(To[u]);
            Cut(u,To[u]); makeroot(tmp);
        } else {
            access(E[rt]),splay(E[rt]); int k=u;
            while (nroot(k)) k=fa[k];
            if (k==E[rt]) Cut(u,To[u]),Link(rt,E[rt]),E[rt]=0,makeroot(u);
            else {
                int tmp=Findroot(To[u]);
                Cut(u,To[u]); makeroot(tmp);
            }
        }
    }

    To[u]=x;
    if (Findroot(To[u])==Findroot(u)) makeroot(u),E[u]=To[u];
    else {
        int tmp=Findroot(To[u]);
        Link(u,To[u]); makeroot(tmp);
    }

    splay(u); w[u]=i; pushup(u);
    if (u==1 || To[u]==1) S.insert(w[u]);
}
inline int qry(int u){
    int rt=Findroot(u);
    if (!E[rt]) return n+1;
    else {
        access(u),splay(u); int ret=val[u]; //val 为维护出来的实链点权 max
        access(E[rt]),splay(E[rt]); ret=max(ret,val[E[rt]]);
        return ret;
    }
}
int main(){
    scanf("%d%d",&n,&m); pw[0]=1;
    for (int i=1; i<=n; i++) pw[i]=pw[i-1]*2%mod;
    for (int i=1; i<=n; i++){
        scanf("%d%s",&d[i],s);
        for (int j=0; j<m; j++) sta[i]|=(s[j]-'0')<<j;
    }
    for (int i=n; i>=1; i--){
        upd(sta[i]+1,(sta[i]^(1<<(d[i]-1)))+1,i);
        int tim=qry(1),k=n+1;
        for (int j=0; j<m; j++) k=min(k,qry((1<<j)+1));
        ans=(ans+1ll*pw[i]*(tim-i))%mod;
        int mn=min(k,(S.empty()?n+1:*S.begin()));
        ans=(ans+1ll*pw[i]*(mn-i))%mod;
    }
    printf("%d\n",ans);
}