一、题目
二、解法
首先拆限制，看似他给的是区间相等，其实是若干组单点相等。
那么把单点的限制用并查集连起来，我们只需要关系联通块个数即可。
问题转化为了每次给两个区间，要求区间对应位连边。线段树优化建图做不了，但是 (st) 表可以，设 (fa[i][j]) 表示以 (i) 为左端点，长度为 (2^j) 区间的并查集，我们把这个看成节点，但他的作用实际上是打标记。
初始化 (fa[i][..]=i)，打标记时直接把标记节点的并查集连起来，最后还需要下传一次，对于点 ((i,j))，我们找到他在并查集上的父亲 ((x,j))，然后把 ((i,j-1),(x,j-1)) 和 ((i+2^{j-1},j-1),(x+2^{j-1},j-1)) 分别连起来即可。
三、总结
(st) 表对位优化建图可以当做一个小套路记下来，但是倍增是真的强，在区间问题中我们要主动使用它。
#include <cstdio>
const int M = 100005;
const int MOD = 1e9+7;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,ans,fa[M][20];
int find(int x,int y)
{
if(fa[x][y]!=x) fa[x][y]=find(fa[x][y],y);
return fa[x][y];
}
void merge(int x,int y,int k)
{
int u=find(x,k),v=find(y,k);
fa[u][k]=v;
}
signed main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
for(int j=0;j<=19;j++)
fa[i][j]=i;
for(int i=1;i<=m;i++)
{
int l1=read(),r1=read(),l2=read(),r2=read();
for(int j=19;j>=0;j--)
if(l1+(1<<j)-1<=r1)
{
merge(l1,l2,j);
l1+=(1<<j);l2+=(1<<j);
}
}
for(int j=19;j>=1;j--)
for(int i=1;i+(1<<j)-1<=n;i++)
{
int x=find(i,j);
merge(i,x,j-1);
merge(i+(1<<j-1),x+(1<<j-1),j-1);
}
for(int i=1;i<=n;i++)
if(fa[i][0]==i)
ans=!ans?9:(ans*10ll%MOD);
printf("%d
",ans);
}