310-02-ACOJ-1873-限制数字

题目描述：

一个长度为n的大数，用$S_1,..S_n$表示，其中$S\_i$表示数的第i位，$S_1$是数的最高位。
现告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1} … S_{r_1}$与$S_{l_2} … S_{r_2}$完全相同。
给定限制条件后，问满足以上所有条件的数有多少个。

题解：

首先考虑没有限制的情况是怎么样的，在没有限制的情况之下，所有的可能的情况应该是第一位数字有九种可能性（不可以是0），其余的各位都有十种可能性，将每位的种数相乘（小学问题）

而现在加上了限制条件，无非就是某几位的可能型变得一样了。

这个时候我们就可以使用并查集，如果某两个数字应该是相同的，那么就合并，最后的答案应该就是并查集的个数的$10$连乘（这里没有考虑首位为$9$的情况，这在后文会考虑到）。

但是很遗憾，单独直接使用并查集肯定会超时，时间复杂度为$O(n^2)$。而解决这一问题的方法就是使用二进制优化这一手段。

这里还是使用倍增的思想，我们可以对并查集的每个组编号。而且并查集的储存方式也要进行改变。

定义：

$f[i][j]$是起点为$i$区间$2^j$，即$1<

$fa[i]$表示第$i$个区间的父亲（并查集所需要的数组）

$s[i]$表示以$i$为编号的区间的起点位置（代码中需要知道所以要存）

步骤：

1. 读入 + 预处理数组（这非常好做）

2. 读入限制条件 —> 对“大区间”进行处理把区间简化为尽量少项数的$2^i$之和

3. 下放约束条件：前面只对“大区间”进行了$merge$

   现在要从大到小，对每个区间拆分为两个区间，两两$merge$

   举个形象的例子：$[3,6]$与$[9,12]$这两个区间在并查集当中是合并的，但是$[3,4],[9,10]$和$[5,6],[11,12]$并没有被合并，这就是下放的意义，因为我们最后统计的是长度为$1$的区间的并查集当中的个数

4. 最后第一位的$ans=9$，然后从第二位开始遍历，求答案。

#include 
#include 
#define int long long

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e9 + 7;
// s[i]表示以i为编号的区间的起始位置, fa[i]表示i的并查集的父亲, f[i][j]是i为起点1< q) swap(p, q);
    fa[q] = p;
}

signed main() {
    cin >> n >> m;
    pre_work();
    for (int i = 1; i <= m; i ++) {
        int l1, l2, r1, r2; cin >> l1 >> r1 >> l2 >> r2;
        for (int k = log2(r1 - l1 + 1); k >= 0; k --)
            // 判断这次的区间长度不会超过, 不然下一个k
            if (l1 + (1 << k) - 1 <= r1) {
                    merge(l1, l2, k);
                    l1 += (1 << k); l2 += (1 << k);
            }
    }
        // 约束条件下放
    int tmp, tmps;
    for (int k = log2(n) + 1;  k; k --)
        for (int i = 1; i + (1 << k) - 1 <= n; i ++) {
            tmp = get(f[i][k]); tmps = s[tmp];
            merge(i, tmps, k - 1); merge(i + (1 << (k - 1)), tmps + (1 << (k - 1)), k - 1);
        }

    int ans = 9;
    for (int i = 2; i <= n; i ++)
        if (fa[f[i][0]] == f[i][0])
            ans = (ans * 10) % P;
    cout << ans << endl;
    return 0;
}

这段代码值得注意：

void merge(int x, int y, int k) {
    int p = get(f[x][k]), q = get(f[y][k]);
    if (p > q) swap(p, q);
    fa[q] = p;
}

由于$k$是一样的，所以区间序号上，$p,q$“同阶”，就意味着$x y \rightarrow p > q$

在合并区间的过程中，为了保证父亲区间永远在前面（因为先统计了第一位的$9$），所以必须要以这个逻辑来写。

下面为错误方法，请勿模仿（去掉了高亮）：

void merge(int x, int y, int k) {
    int p = get(f[x][k]), q = get(f[y][k]);
    if (p < q) fa[q] = p;
    else fa[p] = q;
}