bzoj4569 [Scoi2016]萌萌哒 （st表 维护 并查集）

萌萌哒 （st表 维护 并查集）"/>

bzoj4569 [Scoi2016]萌萌哒 （st表 维护 并查集）

bzoj4569 [Scoi2016]萌萌哒

原题地址：.php?id=4569

题意：
一个长度为n的大数，用S 1 $_1$S 2 $_2$S 3 $_3$…S n $_n$表示，其中S i $_i$表示数的第i位，S 1 $_1$是数的最高位。
告诉你一些限制条件，每个条件表示为四个数，l 1 $_1$，r 1 $_1$，l 2 $_2$，r 2 $_2$，即两个长度相同的区间，表示子串S l1 $_{l1}$S l1+1 $_{l1+1}$S l1+2 $_{l1+2}$..S r1 $_{r1}$与S l2 $_{l2}$S l2+1 $_{l2+1}$S l2+2 $_{l2+2}$..S r2 $_{r2}$完全相同。比如n=6时，某限制条件l 1 $_1$=1，r 1 $_1$=3，l 2 $_2$=4，r 2 $_2$=6，那么123123，351351均满足条件，但是12012，131141不满足条件，前者数的长度不为6，后者第二位与第五位不同。
问满足以上所有条件的数有多少个。

数据范围
1≤n≤10^5，1≤m≤10^5，1≤li1,ri1,li2,ri2≤n；并且保证ri1-li1=ri2-li2。

题解：
（今天的t2）
首先我们看到题，想到维护并查集。
如果最后有cnt个并查集，那么答案是 9*10^（cnt-1）（mod）
特别地，n=1 时 ans=10。
但是如果每一个限制条件都for一遍区间所有的位置，依次把对应的位置加入并查集，复杂度O(n^2)，显然会TLE。（30‘）
这是因为有很多已经同属一个并查集的点被重复操作了。

我们考虑减少操作的次数，这里有一个巧妙的用ST表维护它的方法：
我们把区间们分成logn层，共n*logn个区间。
id[i][j]是从i位开始的，长度为2^j的一个区间的序号。（[i,i+2^j-1]）
每次给出限制条件，我们可以在logn时间内，把给出的区间拆掉，把这些相对应的拆出的区间加入并查集中。
merge(id[i2][j]，id[i2][j]) 即表示i1位开始的，长度为2^j的一个区间于i2位开始的，长度为2^j的一个区间每一位一 一相同。

如果把长度都为2^j的区间看做一层，现在我们每一层都得到了一些并查集。但是最终我们的答案cnt无疑是去数id[i][0]这一层的并查集个数。
把上一层的关系pushdown：对于长为2^j这一层，即把每个区间拆分成两个长为2^（j-1)的区间。
具体来说：
getfa(id[i][j])区间的起始位置为s，那么merge(id[i][j-1]，id[s][j-1] ) 和 merge(id[i+(1<< j-1)][j-1]，id[s+(1<< j-1)][j-1] )
这样从高层到底层pushdown，最后在id[i][0]这一层数并查集个数即可。

小心i+(1<< j-1)时数组越界。（RE x 2 )

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int mod=1e9+7;
const int N=100005;
const int P=18;
int fa[20*N],id[N][P+10],s[20*N],tail=0,cnt=0;
bool vis[20*N];
int getfa(int x)
{if(fa[x]==x)  return x;else return fa[x]=getfa(fa[x]);
}
int n,m;
LL modpow(LL A,int B)
{LL ans=1; LL base=A;for(;B;B>>=1){if(B&1)ans=((ans%mod)*(base%mod))%mod;base=((base%mod)*(base%mod))%mod;}return ans;
}
void merge(int x,int y)
{int fx=getfa(x); int fy=getfa(y);if(fx!=fy) fa[fx]=fy;
}
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<=P;i++)for(int j=1;j<=n;j++){id[j][i]=++tail; s[tail]=j; fa[tail]=tail;}while(m--){int l,r,L,R;scanf("%d%d%d%d",&l,&r,&L,&R);LL nxt=1<<P;for(int i=P;i>=0;i--,nxt>>=1){if(l+nxt-1<=r){merge(id[l][i],id[L][i]);l+=nxt; L+=nxt;}}}   if(n==1) {printf("10\n"); return 0;}for(int i=P;i>=1;i--){for(int j=1;j<=n;j++){int f=getfa(id[j][i]);if(j+(1<<i)>n) continue;int st=s[f];merge(id[st][i-1],id[j][i-1]);merge(id[st+(1<<i-1)][i-1],id[j+(1<<i-1)][i-1]);}}for(int i=1;i<=n;i++){if(!vis[getfa(id[i][0])]) {vis[getfa(id[i][0])]=1; cnt++;}}LL ans;ans=modpow(10,cnt-1);ans=(ans*9LL)%mod;printf("%lld\n",ans);return 0;
}

话说这题有题面吗，感觉一点都不萌萌哒