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

Problem

【SCOI2016】萌萌哒

Description

一个长度为的大数，用表示，其中表示数的第位，是数的最高位，告诉你一些限制条件，每个条件表示为四个数，，，，，即两个长度相同的区间，表示子串与完全相同。比如时，某限制条件，，，，那么，均满足条件，但是，不满足条件，前者数的长度不为，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

Input

第一行两个数和，分别表示大数的长度，以及限制条件的个数。接下来行，对于第行，有个数，，，，分别表示该限制条件对应的两个区间。
，，；并且保证。

Output

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

Sample Input

4 2
1 2 3 4 
3 3 3 3

Sample Output

90

标签：并查集 ST表

Solution

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

首先朴素思想是用并查集维护每位的相同关系，每次暴力合并，最后统计有几个集合就有几个自由元。若有个集合，那么答案为。

发现我们花费了很多时间再合并上，考虑用带数据结构优化合并。这里需要用到表。
考虑存组并查集，第组并查集的第个元素维护的是区间与其他长度为的区间是否相同。这样对于关系，令，等同于和，那么合并第组并查集中的和、第组并查集中的和即可。随后像表一样自大区间向小区间合并信息，可得出最后的集合个数，计算答案即可。

Code

#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;
}