自动搬运

查看原文

来自洛谷，原作者为

	wishapig 最黑的那段路，终究是要自己走完的

搬运于2025-08-24 22:46:17，当前版本为作者最后更新于2023-04-05 22:00:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

题目大意

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

不断进行以下操作：

• 取出编号最小的 $S$ 为空的元素 $(d_*,S_*)$
• 把所有的元素的 $S$ 替换成 $S\oplus \{d_*\}$

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

对每个 $[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$ 出发能到一个环。

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

• $0$ 处于一个内向基环树中，那么答案为 $0$。
• $0$ 不在内向基环树中：
  • $0$ 所在弱连通块大小 $\ge 2$，那么答案为 $1$。
  • $0$ 为一个孤点：
    • 若某个 $\operatorname{popcnt}=1$ 的点在一个内向基环树中，那么答案为 $1$。
    • 否则，答案为 $2$。

这样，枚举 $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$ 从大到小扫描线，$S$ 相同的体现为修改出边指向的节点。

那么我只需要分别求出从 $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$

• $u,t$ 在同一个弱连通块内，则把树根定为 $u$，并记录附加边。
• 否则，正常连边，连边后整个弱连通块的根定为原 $t$ 所在弱连通块的根。

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

最后一部分是查询：

• 先查出 $u$ 所在弱连通块的根，若其没有附加边则为内向树，返回 $n+1$。
• 否则，求出 $u$ 到根路径的点权 $\max$，和环上点权 $\max$，取大的那个返回即可。

时间复杂度为 $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);
}