一个长度为 nn 的大数, 每次告诉你两个长度相同的区间数字完全对应相同, 问可能的数的个数。

n≤105n \le 10^5

LOJ2014

Solution

暴力做法是用并查集维护，每次对两区间的对应点合并，答案即为10cnt−1×910^{cnt-1} \times 9（最高位不为00）

考虑用倍增优化这个过程

类似于ST表的做法，每次只对[l,l+2k−1][l, l + 2^{k} - 1]，[r−2k+1,r][r - 2^k + 1, r]这两个区间打上标记

最后再从上往下扫一遍下传标记即可

Summary

这个做法好巧妙

有点类似于线段树优化建边的思想，只不过换成了并查集

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e5 + 100;
const int Mod = 1e9 + 7;

int N, M;

inline int Pow (int a, int b)
{
	int ans = 1;
	for (int i = b; i; i >>= 1, a = (LL) a * a % Mod) if (i & 1) ans = (LL) ans * a % Mod;
	return ans;
}

namespace ST
{
	int Log[Maxn];
	struct info
	{
		int ch[2];
	} node[Maxn * 20];
	int Id[20][Maxn];
	int node_cnt;

	namespace DSU
	{
		int fa[Maxn * 20];
		inline void init (const int &n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
		inline int get_fa (const int &x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }
		inline void link (const int &x, const int &y) { fa[get_fa (x)] = get_fa (y); }
	}

	inline void init ()
	{
		Log[1] = 0; for (int i = 2; i <= N; ++i) Log[i] = Log[i >> 1] + 1;
		for (int i = 1; i <= N; ++i) Id[0][i] = ++node_cnt;
		for (int i = 1; i <= Log[N]; ++i)
			for (int j = 1; j + (1 << i) - 1 <= N; ++j)
			{
				Id[i][j] = ++node_cnt;
				node[Id[i][j]].ch[0] = Id[i - 1][j];
				node[Id[i][j]].ch[1] = Id[i - 1][j + (1 << (i - 1))];
			}

		DSU :: init (node_cnt);
	}

	inline void merge (const int &l1, const int &r1, const int &l2, const int &r2)
	{
		int k = Log[r1 - l1 + 1];
		DSU :: link (Id[k][l1], Id[k][l2]);
		DSU :: link (Id[k][r1 - (1 << k) + 1], Id[k][r2 - (1 << k) + 1]);
	}

	inline void flush ()
	{
		for (int i = Log[N]; i >= 1; --i)
			for (int j = 1; j + (1 << i) - 1 <= N; ++j)
			{
				int f = DSU :: get_fa (Id[i][j]);
				DSU :: link (node[Id[i][j]].ch[0], node[f].ch[0]);
				DSU :: link (node[Id[i][j]].ch[1], node[f].ch[1]);
			}

		int ans = 0;
		for (int i = 1; i <= N; ++i) if (DSU :: fa[i] == i) ++ans;
		cout << (LL) Pow (10, ans - 1) * 9 % Mod << endl;
	}
}

inline void Solve ()
{
	ST :: init ();
	while (M--)
	{
		int l1 = read<int>(), r1 = read<int>(), l2 = read<int>(), r2 = read<int>();
		ST :: merge (l1, r1, l2, r2);
	}
	ST :: flush ();
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}