Liveddd's Blog

愛にできることはまだあるかい

P3295 [SCOI2016] 萌萌哒

发表于 更新于 分类于
本文字数： 2k 阅读时长 ≈ 4 分钟

最开始觉得挺巧妙的，但回看这题其实挺套路的。

我们考虑暴力用并查集合并每个相等的位置，这样时间复杂度为 $\mathcal O(nm)$。

注意到区间相等的限制显然满足结合律，并且可以拆成若干个单独的连续小区间。

我们考虑一个类似于倍增的想法，尝试将每对 限制区间 按照长度进行二进制拆分，拆分成若干对 长度为 $2^i$ 的限制区间。从大到小枚举 $i$ ，每次对长度 $2^i$ 的限制区间进行合并，之后下传到长度为 $2^{i-1}$ 的限制区间上去。 这个过程有点类似 ST 表的拆分，而下传过程中类似于线段树的懒标记。总的时间复杂度为 $\mathcal O((n+m)\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
const int N=1e5+10,mod=1e9+7,K=25;
template <class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();};
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template <class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}

int n,m;
ll ans=9;
int fa[N][K];
int find(int x,int k)
{
    return fa[x][k]==x?x:fa[x][k]=find(fa[x][k],k);
}
void merge(int x,int y,int k)
{
    x=find(x,k),y=find(y,k);
    if(x!=y)fa[y][k]=x;
}
int main()
{
    read(n,m);
    int k=log(n)/log(2)+1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
            fa[i][j]=i;
    for(int i=1;i<=m;i++)
    {
        int l1,r1,l2,r2;
        read(l1,r1,l2,r2);
        int len=r1-l1+1;
        for(int j=k;~j;j--)
            if(len>>j&1)
                merge(l1,l2,j),l1+=1<<j,l2+=1<<j;
    }
    for(int j=k;j;j--)
        for(int i=1;i+(1<<j)<=n+1;i++)
        {
            int pos=find(i,j);
            merge(i,pos,j-1),merge(i+(1<<j-1),pos+(1<<j-1),j-1);
        }
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(find(i,0)==i&&++cnt>1)
            ans=ans*10%mod;
    printf("%d\n",ans);
    return 0;
}