依旧求条
原题链接：21425.萌萌哒
2026-01-24 10:32:10
发布于：浙江
31阅读
0回复
0点赞
lg可过，这里全RE。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e7 + 10, mod = 1e9 + 7;
int n, m, fa[maxn][20];
int find(int x, int k) {
return (fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k));
}
void Union(int x, int y, int k) {
int rx = find(x, k), ry = find(y, k);
if (rx == ry) return;
fa[rx][k] = ry;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
int maxk = log2(n);
for (int i = 1; i <= n; i++)for (int k = 0; k <= maxk; k++) fa[i][k] = i;
for (int i = 1, l1, l2, r1, r2; i <= m; i++) {
cin >> l1 >> r1 >> l2 >> r2;
if (l1 == l2 && r1 == r2) continue;
for (int k = maxk; k >= 0; k--) {
int l = 1 << k;
if (l > r1 - l1 + 1) continue;
Union(l1, l2, k);
l1 += l, l2 += l;
}
}
for (int k = maxk; k >= 1; k--) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
int r = find(i, k);
int l = 1 << (k - 1);
Union(i, r, k - 1);
if (i + l <= n) Union(i + l, r + l, k - 1);
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) if (find(i, 0) == i) cnt++;
int ans = 9;
for (int i = 1; i < cnt; i++) ans = ans * 10 % mod;
cout << ans;
return 0;
}
有帮助，赞一个