洛谷P3295 [SCOI2016] 萌萌哒题解

题目链接：P3295 [SCOI2016] 萌萌哒

题意：

一个长度为 $n$ 的大数，用 $S_1S_2S_3 \cdots S_n$表示，其中 $S_i$ 表示数的第 $i$ 位， $S_1$ 是数的最高位。

告诉你一些限制条件，每个条件表示为四个数 $l_1,r_1,l_2,r_2$ ，即两个长度相同的区间，表示子串 $S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}$ 与 $S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$ 完全相同。

比如 $n=6$ 时，某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$ ，那么 $123123$，$351351$ 均满足条件，但是 $12012$，$131141$ 不满足条件，前者数的长度不为 $6$ ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入格式：

第一行两个数 $n$ 和 $m$，分别表示大数的长度，以及限制条件的个数。

接下来 $m$ 行，对于第 $i$ 行，有 $4$ 个数 $l_{i_1},r_{i_1},{l_{i_2}},r_{i_2}$，分别表示该限制条件对应的两个区间。

输出格式：

一个数，表示满足所有条件且长度为 $n$ 的大数的个数。

答案可能很大，因此输出答案模 $ 10^9+7 $ 的结果即可。

数据范围：

$1\le n\le 10^5,~1\le m\le 10^5,~1\le l_{i_1},r_{i_1},{l_{i_2}},r_{i_2}\le n$ ，并且保证 $r_{i_1}-l_{i_1}=r_{i_2}-l_{i_2}$ 。

首先相同的位置可以用并查集维护，这样就是 $\mathcal{O}(n^2)$ 的。

由于并查集是有结合律的，而我们每次都在合并两条等长的线段，所以考虑倍增。

设 $f(i,j)$ 表示 $[j, j + 2^i - 1]$ 的等价类集合。相当于给一个点开了 $i$ 个并查集以维护各个长度的线段。

对于每个询问考虑合并 $f(k,l)$ 和 $f(k, r - 2^k + 1)$ ，其中 $k= \log_2(r-l+1)$

不过因为我们只合并了区间的最上层，我们还需要 push_down 合并的结果。

比如 $f(i,j)=x$ ，那么把 $f(i-1,j)$ 和 $f(i-1,x)$ 合并，$f(i-1,j + 2^{i-1})$ 和 $f(i-1,x+2^{i-1})$ 合并即可

可以证明，每次只合并上层最后下放不会产生冲突，于是我们可以询问完再下放标记。（并查集的结合律）

一边操作一边下放好像也行，不过这样复杂度就变成了 $\mathcal{O}((n + m) \log n\cdot \alpha(n))$ ，没意义。

最后答案就是 $9\times 10^{T-1}$ ，其中 $T$ 表示 $f(0,j)$ 的不同等价类的个数，乘 $9$ 是因为不能有前导零。

因此时间复杂度 $\mathcal{O}(n \log n \cdot \alpha(n) + m \alpha(n))$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int lg[N], fa[19][N], sz[19][N]; char vis[N];
int find(int k, int x)
{
    if(fa[k][x] == x) return x;
    return fa[k][x] = find(k, fa[k][x]);
}
ll qpow(int b, ll a = 10)
{
    ll r = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 2; i <= N - 5; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 0; i <= lg[n]; i++)
        for(int j = 1; j + (1 << i) - 1 <= n; j++) { fa[i][j] = j, sz[i][j] = 1; }
    for(int i = 1, l1, r1, l2, r2; i <= m; i++)
    {
        cin >> l1 >> r1 >> l2 >> r2;
        int k = lg[r1 - l1 + 1];
        int a = find(k, l1), b = find(k, l2);
        if(sz[k][a] > sz[k][b]) { swap(a, b); } sz[k][b] += sz[k][a]; fa[k][a] = b;
        int c = find(k, r1 - (1 << k) + 1);
        int d = find(k, r2 - (1 << k) + 1);
        if(sz[k][c] > sz[k][d]) { swap(a, b); } sz[k][d] += sz[k][c]; fa[k][c] = d;
    }
    for(int i = lg[n]; i; i--)
    {
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
        {
            int f = find(i, j); if(f == j) continue;
            int a = find(i - 1, j), b = find(i - 1, f);
            if(sz[i - 1][a] > sz[i - 1][b]) { swap(a, b); } sz[i - 1][b] += sz[i - 1][a]; fa[i - 1][a] = b;
            int c = find(i - 1, j + (1 << (i - 1)));
            int d = find(i - 1, f + (1 << (i - 1)));
            if(sz[i - 1][c] > sz[i - 1][d]) { swap(c, d); } sz[i - 1][d] += sz[i - 1][c]; fa[i - 1][c] = d;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        int f = find(0, i);
        if(!vis[f]) { vis[f] = true; ++cnt; }
    }
    cout << 9ll * qpow(cnt - 1) % mod << '\n';
    return 0;
}