真的好久好久没写题解啦……真是不好意思！
emmm……立刻岔开话题……
这道题真的是一道很好很好的倍增优化并查集的题！
首先对于暴力，就是每一个点都暴力并查集，每一次判断这个点的祖先是不是自己就可以了，30分。
我么当然不能止步于30分啊，所以自然要想想优化啦！
我一开始是想单独考虑每一个子问题，考虑这段区间是否包含原来修改的部分，但是发现需要维护的东西太多了……不能简单明了的解决问题。
再回头看看题面，我们由于不能每一次都一个个地维护每一个点的并查集，就想到了倍增优化。
对于状态 fa [ i ] [ j ] 意思是从 i 开始 2j - 1 的长度，i 的父亲是谁（和 i 相同的区间左端点）。 那么我们只要将这段区间拆成若干个（logn）个子区间，再一一对应维护并查集即可。
由于我们最后是要小的状态 fa [ i ] [ 0 ]，所以对于一个区间的父亲，我们再分别将父亲的状态分开再转给儿子，就保证了最后能维护到最短的这个区间（长度为1，fa [ x ] [ 0 ] ）。
最后统计独立点个数就行。
代码：
#include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<algorithm> #include<cstring> #include<vector> using namespace std; #define maxn 100005 #define int long long const int mod = 1e9+7; int fa[maxn][25]; int n,m; int find(int x,int i) { return x == fa[x][i] ? x : fa[x][i] = find(fa[x][i],i); } void merge(int x,int y,int i) { x=find(x,i); y=find(y,i); if(x!=y) fa[x][i]=y; } main() { int ans=9; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) for(int j=0;j<=20;j++) fa[i][j]=i; for(int i=1;i<=m;i++) { int l1,r1,l2,r2; scanf("%lld%lld%lld%lld",&l1,&r1,&l2,&r2); for(int j=20;j>=0;j--) { if(l1+(1<<j)-1<=r1) { merge(l1,l2,j); l1+=(1<<j); l2+=(1<<j); } } } for(int j=20;j;j--) for(int i=1;i+(1<<j)-1<=n;i++) { int st=find(i,j); if(st==i) continue; merge(i,st,j-1); merge(i+(1<<j-1),st+(1<<j-1),j-1); } int num=0; for(int i=1;i<=n;i++) if(i==fa[i][0]) num++; for(int i=1;i<num;i++) (ans*=10)%=mod; printf("%lld",ans); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/10686545.html