4569: [Scoi2016]萌萌哒
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 1554 Solved: 791
[Submit][Status][Discuss]
Description
Input
Output
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模10^9+7的结果即可。
Sample Input
1 2 3 4
3 3 3 3
Sample Output
HINT
Source
Solution
妙题。
维护相等关系怎么办？
各种匹配都用不上。
感到无从下手。
我们就不考虑区间相等的问题了。
转化研究对象，
区间相等本质上是点的对应相等。
而一些点的位置都要相等的话，那么只能取同样的一个值。具体是哪个值没有关系。（当然不能前导零）
维护相等关系，用并查集。
所以，我们可以枚举所有的位置，每个位置开始是一个联通块。
再对每一个位置枚举所有条件，然后合并。答案就是9*10^(num-1) num为联通块的个数。
O（n^2）
这样合并太暴力了。
但是最后的查询只有O(n)
我们考虑均衡到O(nlogn)
一个浪费的地方在于，我们每个点要枚举所有的询问，其实这个询问是一个区间相等的关系。
能不能直接把区间相等直接用并查集并起来呢？
灵活的拆分区间，
可以比较自然地想到倍增。
所以，我们也可以把并查集利用倍增来进行实现。
把每个位置拆成logn个点。
第i个点，表示，x开始，连续2^i的子串。
两个条件相等，就二进制拆分成logn个区间，然后对应的并查集合并。
O（nlogn询问）
最后查询答案呢？
如果知道最后的每个点的相等关系就容易处理了。
我们可以拆分并查集。
2^N=2^(N-1)+2^(N-1)
从大到小枚举所有的nlogn个并查集点。
对于并查集的点k，把k的父亲找出来，自己和父亲代表的区间都拆成两半，前后部分分别再并起来。
复杂度O(nlogn)
其实，我们就是用倍增拆点的并查集维护了区间相等关系。
可以比较快地拆分区间，最后的并查集拆分复杂度也有保证。
其实感觉挺类似线段树的（虽然线段树不是二进制拆分）
都是把区间拆分。
用大的区间合并而不再往下分，就类似线段树的懒标记。
最后到叶子，就是懒标记下放。
update：2018.12.8
更具体地来考虑复杂度为什么变优秀了：
最后一共其实就是一棵并查集树，每个点只有一个father
但是期间每次枚举区间的O(n^2)的话，平均每个点要规定O(n)次father，其实最后就只需要一个。
这种倍增并查集的方式，本质上对这些关系进行了压缩。只有O(logn)个了。
通过合并冗余的关系，减少过程中的关系调整次数，就得到了优秀的复杂度。
（其实懒标记也是这样的）
代码：
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') #define num(x,y) (y*n+x) using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=1e5+5; const int mod=1e9+7; int n,m; int fa[N*20]; bool buc[N]; int fin(int x){ return fa[x]==x?x:fa[x]=fin(fa[x]); } void merge(int x,int y){ int k1=fin(x),k2=fin(y); if(k1!=k2) fa[k1]=k2; } int main(){ rd(n);rd(m); for(reg i=1;i<=n*20;++i) fa[i]=i; int l1,r1,l2,r2; for(reg i=1;i<=m;++i){ rd(l1);rd(r1);rd(l2);rd(r2); int len=r1-l1+1; for(reg j=19;j>=0;--j){ if(len>=(1<<j)){ merge(num(l1,j),num(l2,j)); l1+=(1<<j),l2+=(1<<j); len-=(1<<j); } } } for(reg j=19;j>=1;--j){ for(reg i=1;i<=n;++i){ if(i+(1<<j)-1>n) break; int to=fin(num(i,j)); merge(num(i,(j-1)),to-n); merge(num(i+(1<<(j-1)),(j-1)),to-n+(1<<(j-1))); } } ll ans=9; ll cnt=0; for(reg i=1;i<=n;++i){ int k=fin(num(i,0)); if(!buc[k]) buc[k]=1,++cnt; } for(reg i=1;i<=cnt-1;++i){ ans=(ans*10)%mod; } printf("%lld",ans); return 0; } } int main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/8 15:01:18 */