BZOJ

# 解析

$Union(belong_{i - 1}[j], belong_{i - 1}[k]), Union(belong_{i - 1}[j + 2^{i - 1}], belong_{i - 1}[k + 2^{i - 1}])$

# 个人对倍增原理的理解

$[l, l + 2^{p_0}), [l + 2^{p_0}, l + 2^{p_0} + 2^{p_1}),[l + 2^{p_0} + 2^{p_1}, l + 2^{p_0} + 2^{p_1} + 2^{p_2}), ……(p0 > p1 > p2 > ……)$

# （丑陋的）代码

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 100005

typedef long long LL;
const int mod = (int)1e9 + 7;

void merge(int, int, int, int);
void push_down();
int qpower(int, int);

int N, M, ans;
struct DSU {
int belong[18][MAXN];
void init(int = 0);
int find(int dep, int x) { return belong[dep][x] == x ? x : belong[dep][x] = find(dep, belong[dep][x]); }
bool merge(int dep, int x, int y) {
x = find(dep, x), y = find(dep, y);
if (x == y) return 0;
belong[dep][x] = y;
return 1;
}
} dsu;

int main() {
std::ios::sync_with_stdio(0);
std::cin >> N >> M;
dsu.init(N);
while (M--) {
int l1, r1, l2, r2;
std::cin >> l1 >> r1 >> l2 >> r2;
merge(l1, r1, l2, r2);
}
push_down();
for (int i = 1; i <= N; ++i) if (dsu.belong[0][i] == i) ++ans;
printf("%lld\n", 9ll * qpower(10, ans - 1) % mod);

return 0;
}
void merge(int l1, int r1, int l2, int r2) {
for (int i = 17; i >= 0; --i)
if ((1 << i) <= r1 - l1 + 1) {
dsu.merge(i, l1, l2);
l1 += (1 << i), l2 += (1 << i);
}
}
void push_down() {
for (int i = 17; i; --i) for (int j = 1; j + (1 << i) - 1 <= N; ++j) {
int fa = dsu.find(i, j);
if (fa ^ j) dsu.merge(i - 1, j, fa), dsu.merge(i - 1, j + (1 << i - 1), fa + (1 << i - 1));
}
}
void DSU::init(int n) {
for (int i = 17; i >= 0; --i) for (int j = 1; j + (1 << i) - 1 <= n; ++j) belong[i][j] = j;
}
int qpower(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = (LL)res * x % mod;
x = (LL)x * x % mod, y >>= 1;
}
return res;
}
//Rhein_E

bzoj4569[SCOI2016]萌萌哒（倍增+并查集）

(0)
(0)

0条