[SCOI2016]萌萌哒【并查集】【倍增】

萌萌哒【并查集】【倍增】"/>

[SCOI2016]萌萌哒【并查集】【倍增】

>Link

luogu P3295

>Description

n , m ≤ 1 0 5 n,m\le10^5 n,m≤105

>解题思路

我感觉这道题的操作跟 这道题 好像

一开始的想法：两个区间完全相同，说明两个区间每个对应的数字相同，可以搞一个并查集将这些数字并起来，最后并查集的数量就是可以不同的数的个数，答案用快速幂计算一下
但是这样的时间复杂度为 O ( n 2 l o g n ) O(n^2logn) O(n2logn)，显然不行

正解就是倍增优化并查集的过程
正常的并查集为 f a i fa_i fai​ 表示 i i i 所属的集，这里用倍增， f a g , i fa_{g,i} fag,i​ 表示区间 [ i , i + 2 g − 1 ] [i,i+2^g-1] [i,i+2g−1] 所属的集（把一个点分成 l o g n logn logn 个点）
每次操作，我们就把 [ l 1 , r 1 ] , [ l 2 , r 2 ] [l_1,r_1],[l_2,r_2] [l1​,r1​],[l2​,r2​] 区间都分成两个 2 2 2 的次幂的区间，把对应相同的区间并在一起，最后我们再从大到小把区间间的关系往下传。下传操作也是一样的，原区间分成两个区间，然后把对应相同的部分并在一起
最后并查集的数量就是 f a 0 , i fa_{0,i} fa0,i​ 的数量

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define N 100010
using namespace std;const LL Mod = 1e9 + 7;
int n, m, fa[20][N], lg[N], sum;int find (int g, int now)
{if (fa[g][now] == now) return now;return fa[g][now] = find (g, fa[g][now]);
}
void connect (int g, int x, int y)
{if (x == y) return;int fx = find (g, x), fy = find (g, y);if (fx != fy) fa[g][fx] = fy;
}
void pushdown (int g, int x)
{int fx = find (g, x);connect (g - 1, x, fx);connect (g - 1, x + (1 << (g - 1)), fx + (1 << (g - 1)));
}
LL power (LL aa, LL bb)
{LL ret = 1;for (aa %= Mod; bb; bb >>= 1, aa = aa * aa % Mod)if (bb & 1) ret = ret * aa % Mod;return ret;
}int main()
{int g, l, r, ll, rr;scanf ("%d%d", &n, &m);for (int i = 1; i <= n; i++)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);for (int i = 1; i <= n; i++) lg[i]--;for (int i = 0; i <= lg[n]; i++)for (int j = 1; j <= n; j++)fa[i][j] = j;for (int i = 1; i <= m; i++){scanf ("%d%d%d%d", &l, &r, &ll, &rr);g = lg[r - l + 1];connect (g, l, ll);connect (g, r - (1 << g) + 1, rr - (1 << g) + 1);}for (int i = lg[n]; i >= 1; i--)for (int j = 1; j <= n - (1 << i) + 1; j++)pushdown (i, j);for (int i = 1; i <= n; i++)if (find (0, i) == i) sum++;sum--;printf ("%lld", (LL)9 * power (10, sum) % Mod);return 0;
}