「SCOI2016」萌萌哒 https://loj.ac/problem/2014
这思路厉害啊..
容易发现有个暴力是并查集
然后我想了半天线段树优化无果
然后正解是倍增优化并查集
有这个思路就简单了, 就是开一个并查集代表每个开头 \(i\) 每个长 \(2^j\) 的区间的归属
然后合并就随便合并
最后需要 \(2^0\) 的信息, 从上面把信息分裂传下来就好了
- Code:
- #include <cstdio>
- #include <cctype>
- const int N=1e5+10;
- template <class T>
- void read(T &x)
- {
- x=0;char c=getchar();
- while(!isdigit(c)) c=getchar();
- while(isdigit(c)) x=x*10+c-'0',c=getchar();
- }
- const int mod=1e9+7;
- int n,m;
- int f[N*18],Id[N][18],pos[N*20],dep[N*20],tot;
- int Find(int a){return f[a]=f[a]==a?a:Find(f[a]);}
- void Merge(int a,int b){f[Find(b)]=Find(a);}
- int main()
- {
- read(n),read(m);
- for(int j=0;j<=17;j++)
- for(int i=1;i<=n;i++)
- Id[i][j]=++tot,f[tot]=tot,pos[tot]=i,dep[tot]=j;
- for(int l1,r1,l2,r2,i=1;i<=m;i++)
- {
- read(l1),read(r1),read(l2),read(r2);
- int d=r1+1-l1;
- for(int j=0;j<=17;j++)
- if(d>>j&1)
- Merge(Id[l1][j],Id[l2][j]),l1+=1<<j,l2+=1<<j;
- }
- for(int j=17;j;j--)
- for(int i=1;i<=n;i++)
- {
- int anc=Find(Id[i][j]);
- if(anc==Id[i][j]) continue;
- int i_=pos[anc];
- Merge(Id[i][j-1],Id[i_][j-1]);
- Merge(Id[i+(1<<j-1)][j-1],Id[i_+(1<<j-1)][j-1]);
- }
- int ans=9,is=0;
- for(int i=1;i<=n;i++) if(Find(Id[i][0])==Id[i][0]) {if(is) ans=10ll*ans%mod;is=1;}
- printf("%d\n",ans);
- return 0;
- }
- 2019.3.5
来源: http://www.bubuko.com/infodetail-2976292.html