依旧求条

原题链接：21425.萌萌哒
userId_undefined
Grapher
题解仙人传道者出题人代码纠察员

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;
}
userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    yxdl1
    出道萌新时间刺客空间掌握者时空双修者枚举·枚举小能手模拟·模拟练习生

    是有很多题洛谷能过ACGO爆掉，ACGO数据的锅

    2026-01-24 来自 浙江

    0

热门讨论