BZOJ4569【SCOI2016】萌萌哒 <并查集+ST表>

Posted on Symbols count in article: 935 Reading time ≈ 3 mins.

Problem

【SCOI2016】萌萌哒

Time  Limit:  20  Sec\mathrm{Time\;Limit:\;20\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

一个长度为nn的大数，用S1S2S3⋯SnS_1S_2S_3\cdots S_n表示，其中SiS_i表示数的第ii位，S1S_1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1l_1，r1r_1，l2l_2，r2r_2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2⋯Sr1S_{l_1}S_{l_1+1}S_{l_1+2}\cdots S_{r_1}与Sl2Sl2+1Sl2+2⋯Sr2S_{l_2}S_{l_2+1}S_{l_2+2}\cdots S_{r_2}完全相同。比如n=6n=6时，某限制条件l1=1l_1=1，r1=3r_1=3，l2=4l_2=4，r2=6r_2=6，那么123123123123，351351351351均满足条件，但是1201212012，131141131141不满足条件，前者数的长度不为66，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

Input

第一行两个数nn和mm，分别表示大数的长度，以及限制条件的个数。接下来mm行，对于第ii行，有44个数li1l_{i_1}，ri1r_{i_1}，li2l_{i_2}，ri2r_{i_2}，分别表示该限制条件对应的两个区间。
1≤n≤1051\le n\le 10^5，1≤m≤1051\le m\le 10^5，1≤li1,ri1,li2,ri2≤n1\le l_{i_1},r_{i_1},l_{i_2},r_{i_2}\le n；并且保证ri1−li1=ri2−li2r_{i_1}-l_{i_1}=r_{i_2}-l_{i_2}。

Output

一个数，表示满足所有条件且长度为nn的大数的个数，答案可能很大，因此输出答案模109+710^9+7的结果即可。

Sample Input

1
2
3
4 2
1 2 3 4 
3 3 3 3

Sample Output

1
90

标签：并查集 ST表

Solution

好题，把基础数据结构玩出了新花样。

首先朴素思想是用并查集维护每位的相同关系，每次暴力合并，最后统计有几个集合就有几个自由元。若有cntcnt个集合，那么答案为Ans=9×10cnt−1Ans=9\times10^{cnt-1}。

发现我们花费了很多时间再合并上，考虑用带log⁡\log数据结构优化合并。这里需要用到STST表。
考虑存log⁡n\log{n}组并查集，第ii组并查集的第jj个元素维护的是区间[j,j+2i][j,j+2^i]与其他长度为2i2^i的区间是否相同。这样对于关系Sl1∼r1=Sl2∼r2S_{l_1\sim r_1}=S_{l_2\sim r_2}，令len=r1−l1=r2−l2len=r_1-l_1=r_2-l_2，等同于Sl1∼(l1+2log⁡len)=Sl2∼(l2+2log⁡len)S_{l_1\sim(l_1+2^{\log{len}})}=S_{l_2\sim(l_2+2^{\log{len}})}和S(r1−2log⁡len)∼r1=S(r2−2log⁡len)∼r2S_{(r_1-2^{\log{len}})\sim r_1}=S_{(r_2-2^{\log{len}})\sim r_2}，那么合并第log⁡len\log{len}组并查集中的l1l_1和l2l_2、第log⁡len\log{len}组并查集中的r1−2log⁡lenr_1-2^{\log{len}}和r2−2log⁡lenr_2-2^{\log{len}}即可。随后像STST表一样自大区间向小区间合并信息，可得出最后的集合个数，计算答案即可。

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
#include <bits/stdc++.h>
#define LOG 20
#define MAX_N 100000
#define MOD 1000000007
using namespace std;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, cnt, LOG2[MAX_N+5], fa[LOG][MAX_N+5];    lnt ans = 9LL;
int getf(int d, int x) {return fa[d][x] == x ? x : fa[d][x] = getf(d, fa[d][x]);}
int main() {
    read(n), read(m);	for (int i = 2; i <= n; i++) LOG2[i] = LOG2[i>>1]+1;
    for (int i = 0; i < LOG; i++) for (int j = 1; j <= n; j++) fa[i][j] = j;
    for (int i = 0, l1, l2, e1, e2, l, d; i < m; i++) {
        read(l1), read(e1), read(l2), read(e2), l = e1-l1+1, d = LOG2[l];
        if (getf(d, l1)^getf(d, l2)) fa[d][fa[d][l1]] = fa[d][l2];
        if (getf(d, l1+l-(1<<d))^getf(d, l2+l-(1<<d)))
            fa[d][fa[d][l1+l-(1<<d)]] = fa[d][l2+l-(1<<d)];
    }
    for (int i = LOG2[n]; i; i--) for (int j = 1; j <= n-(1<<i)+1; j++) {
        if (getf(i-1, j)^getf(i-1, getf(i, j))) fa[i-1][fa[i-1][j]] = fa[i-1][fa[i][j]];
        if (getf(i-1, j+(1<<(i-1)))^getf(i-1, getf(i,j)+(1<<(i-1))))
            fa[i-1][fa[i-1][j+(1<<(i-1))]] = fa[i-1][fa[i][j]+(1<<(i-1))];
    }
    for (int i = 1; i <= n; i++) if (getf(0, i) == i) cnt++;
    for (int i = 1; i < cnt; i++) (ans *= 10LL) %= MOD;
    return printf("%lld\n", ans), 0;
}