点此看题
首先拆限制,看似他给的是区间相等,其实是若干组单点相等。
那么把单点的限制用并查集连起来,我们只需要关系联通块个数即可。
问题转化为了每次给两个区间,要求区间对应位连边。线段树优化建图做不了,但是 \(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\n",ans); }