[SCOI2016]萌萌哒_牛客博客

题目描述

一个长度为n的大数，用S1S2S3...Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...Sr2完全相同。
比如n=6时，某限制条件l1=1，r1=3，l2=4，r2=6，那么123123，351351均满足条件，但是12012，131141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

题解：

并查集+倍增
参考题解
 参考
思路：
题目要求[l1,r1]和[l2,r2]区间内相等,那我们可以将对应位置加入到同一个并查集里，合并l1+i和l2+i，i的范围是0到区间长度-1
在同一个并查集里的就要求填的数字必须相同
设S为集合数量
sum=9* $10^{S-1}$
复杂度是O( $n^{2}$ logn)
优化：
我们可以通过st表，将询问区间拆成若干个小区间，将区间与区间合并，原本是点与点合并，这样效率一下就高了
最后再将区间的信息下放到点上
st[i][k]表示左端点的位置为i，长度为2^{k}的区间所在集合的根的左端点
是不是没明白什么意思？
比如说
区间[5,8]合并到区间[1,4]上，fa[5][2]=1(1是区间[1,4]的左端点，2是区间长度为 $2^{2}$ )
最后计算答案时，将所有层的对应的点合并，将每层和他的上层合并
[i][k-1]与[find(i,k)][k-1]合并
将[i+ $2^{k-1}$ ][k-1]与[find(i,k)+ $2^{k-1}$ ][k-1]合并
详细看图
要将黑***间与绿***间合并
图片说明
可以拆分成两个红***间，两个橙***间合并

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 100050;
int f[N][25];
int read(void) {
    int x = 0;
    char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x;
}
int n, m;
int find(int x,int y) {
    if (f[x][y] == x) return x;
    return f[x][y] = find(f[x][y], y);
} //找爹
inline void merge(int x,int y,int len) {
    int fx = find(f[x][len], len), fy = find(f[y][len], len);
    f[f[fx][len]][len] = fy;
} //合并
int lo[N];
const int P = 1e9+7;
int main() {
    n = read(), m = read();
    lo[0] = -1;
    for (int i = 1;i <= n; i++) lo[i] = lo[i/2]+1; // 预处理log2(k)
    for (int i = 1;i <= n; i++) 
        for (int j = 0;j <= 21; j++) 
            f[i][j] = i;
    while (m--) {
        int l1 = read(), r1 = read(), l2 = read(), r2 = read();
        int len = lo[r1 - l1 + 1];
        merge(l1, l2, len); //分成两个小区间
        l1 = r1 - (1 << len) + 1, l2 = r2 - (1 << len) + 1;
        merge(l1, l2, len);
    }
    for (int len = 21;len >= 1; len--) {
        for (int i = 1;i + (1 << len) - 1 <= n; i++) {
            int fa = find(i, len);
            if (fa != i) {
                merge(i, fa, len-1); //大区间分裂成两个小区间
                merge(i + (1 << (len-1)), fa + (1 << (len-1)), len - 1);
            }
        }
    }
    long long ans = 0;
    for (int i = 1;i <= n; i++) {
        if (f[i][0] == i) {
            if (ans == 0) ans = 9;
            else ans = ans * 10 % P;
        }
    }
    cout << ans % P << endl;
    return 0;
}