又切一道紫题！！！
成功的(看了一吨题解之后)，我A掉了第二道紫题。
好，我们仔细观察，发现这是一个排列组合问题。
有些限定条件，要相等的地方，我们就用并查集并起来。最后一查有多少个并查集，就有多少个位置可供*选择。
所以答案就是10^(并查集数)，去除前导0：*(9/10)
好，这样我们得到了一个O(mn)算法。
然后我们考虑优化：每个区间可能被合并多次。所以我们有两种选择：线段树/ST表。
考虑到这是ST表例题(???????),我们就来个ST表与并查集联动求解...
我们的ufs[i][j]代表在[i][2^j]这个区间内的情况。
然后每次合并的时候都往下合并两个j-1(也可以最后再一起下传标记)
实质上是开了logn个并查集，因为我发现find和merge都不跨层。
题外话：与RE战斗的艰辛历程
交了11次RE，实在是让人感受绝望啊。
两种方法全都RE，所幸刚才我写的时候都查出来错了。
那么先来看看第一种方法：
每次都跟线段树一样恰好标记完最少的节点，最后所有标记一起下传。
#include <cstdio>
using namespace std;
const int N = ;
const int mo = ; int ufs[N][],n,m;
int find(int x,int j)
{
if(ufs[x][j]!=x) ufs[x][j]=find(ufs[x][j],j);
return ufs[x][j];
}
void merge(int x,int y,int j)
{
ufs[find(x,j)][j]=find(y,j);///->!!这里调了一个错，之前是ufs[x][j]=......
return;
} int main()
{
scanf("%d%d",&n,&m);
for(int j=;j<=;j++)
{
for(int i=;i<=n;i++) ufs[i][j]=i;///->!
}
int a,b,c,d;
int md=;
while((<<md)<=n) md++;
md--;
for(int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int j=md;j>=;j--)
{
if(a+(<<j)-<=b) merge(a,c,j),a+=(<<j),c+=(<<j);
}
}
///
for(int j=md;j>=;j--)///这里，RE的罪魁祸首！我之前写的0，结果传进去个j=-1直接挂
{
for(int i=;i+(<<j)-<=n;i++)
{
merge(i,find(i,j),j-);
merge(i+(<<(j-)),find(i,j)+(<<(j-)),j-);
}
}
///
long long ans=;
bool q=false;
for(int i=;i<=n;i++)
{
if(find(i,)==i)
{
if(q) ans=(ans*)%mo;
q=;
}
}
//for(int i=1;i<=n;i++) printf("%d ",find(i,0));
printf("%lld",ans);
return ;
}
AC代码，跑的比下面快一些
第二种思路：
每次都传到底。如果已经在一起就不往下推了。
#include <cstdio>
using namespace std;
const int N = ;
const int mo = ; int ufs[N][],n,m;
int ffind(int x,int j)
{
//if(ufs[x][j]!=x) ufs[x][j]=find(ufs[x][j],j);
//return ufs[x][j];
if(j<) return ;
int ans=x,k;
while(ufs[ans][j]!=ans) ans=ufs[ans][j];
while(ufs[x][j]!=x)
{
k=ufs[x][j];
ufs[x][j]=ans;
x=k;
}
return ans;
}
void mmerge(int x,int y,int j)
{
if(j<) return;///这里控制情况，AC
if(ffind(x,j)==ffind(y,j)) return;
ufs[ffind(x,j)][j]=ffind(y,j);///->!!
mmerge(x,y,j-),mmerge(x+(<<(j-)),y+(<<(j-)),j-);///这里RE!会传入j=-1
return;
} int main()
{
scanf("%d%d",&n,&m);
for(int j=;j<=;j++)
{
for(int i=;i<=n;i++) ufs[i][j]=i;///->!
}
int a,b,c,d;
int md=;
while((<<md)<=n) md++;
md--;
for(int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
for(int j=md;j>=;j--)
{
if(a+(<<j)-<=b) mmerge(a,c,j),a+=(<<j),c+=(<<j);
}
}
/** */
long long ans=;
bool q=false;
for(int i=;i<=n;i++)
{
if(ffind(i,)==i)
{
if(q) ans=(ans*)%mo;
q=;
}
}
//for(int i=1;i<=n;i++) printf("%d ",find(i,0));
printf("%lld",ans);
return ;
}
AC代码
结论：函数里最好写上特判违法情况，保险。