倍增+并查集.

Description

给出一个序列, 有$q$次操作, 每次给出$a, b, l$, 表示对于所有的$0 \ldots i$, 连接$(a+i, b+i)$.

求联通块个数.

(这是抽象过的原题模型)

Solution

我们可以建若干虚拟点表示从位置$i$开始向后$2^j$格的区间.

每次可以连接一些这样的虚拟点.

需要注意一对联通虚拟点的下一层, 也就是两对更短的区间也是联通的, 最后自顶向下合并一遍即可.

代码倒是意外的短

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
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#include <bits/stdc++.h>
#define mod 1000000007
 
using namespace std;
 
const int maxn = 1e+5 + 5;
 
typedef long long ll;
 
int n, m;
int fa[maxn * 20], mp[20][maxn], tot;
int revp[maxn * 20], revl[maxn * 20];
int bin[20];
 
int find(int x) {
  return (!fa[x]) ? x : fa[x] = find(fa[x]);
}
inline void link(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx ^ fy) fa[fx] = fy;
}
inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = (ret * base) % mod;
    index >>= 1;
    base = base * base % mod;
  }
  return ret;
}
inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}
 
int main() {
  n = rd(); m = rd();
  if (n == 1) {
    puts("10");
    return 0;
  }
  int L, R, l, r;
  bin[0] = 1;
  for (int i = 1; i < 20; ++i)
    bin[i] = (bin[i - 1] << 1);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < 20; ++j) {
      mp[j][i] = ++tot;
      revp[tot] = i; revl[tot] = j;
    }
  for (int i = 1; i <= m; ++i) {
    L = rd(); R = rd(); l = rd(); r = rd();
    for (int j = 19; ~j; --j) {
      if (L + bin[j] - 1 <= R) {
        link(mp[j][L], mp[j][l]);
        L += bin[j];
        l += bin[j];
      }
    }
  }
  for (int j = 19; j; --j)
    for (int i = 1; i <= n; ++i) {
      int fx = find(mp[j][i]);
      int p = revp[fx], l = revl[fx];
      link(mp[j - 1][i], mp[l - 1][p]);
      link(mp[j - 1][i + bin[j - 1]], mp[l - 1][p + bin[l - 1]]);
    }
  int blo = 0;
  for (int i = 1; i <= n; ++i)
    if (!fa[mp[0][i]]) blo++;
  ll ans = quick_power(10ll, blo - 1) * 9ll % mod;
  printf("%lld\n", ans);
  return 0;
}