文章目录

洛谷 P3295 萌萌哒 做题笔记

发布于

题意

有一个 $n$ 位的大数,有 $m$ 个限制。
每个限制 $\left[l1, r1, l2, r2\right]$ 表示大数的 从左往右数第 $l1$ 位 到 从左往右数第 $r1$ 位,与 大数的 从左往右数第 $l2$ 位 到 从左往右数第 $r2$ 位 完全一致。
求有多少数满足限制。

$1 \leq n, m \leq 10^5$

题解

并查集维护倍增结构。

假设我们有一个 $5$ 位的数,我们维护下面这个结构:

          10[1, 4]   11[2, 5]
   6[1, 2] 7[2, 3]  8[3, 4] 9[4, 5]
1[1, 1] 2[2, 2] 3[3, 3] 4[4, 4] 5[5, 5]

解释一下,最下面一层(第三层)里,每个节点维护的区间长度为 $1$。中间一层(第二层)里,每个节点维护的区间长度为 $2$(第三层的两倍)。最上面的一层(第一层),每个节点维护的区间长度为 $4$(第二层的两倍)。

我们考虑合并 $\left[1, 3\right]$ 和 $\left[3, 5\right]$:
将 $6$ 号节点与 $8$ 号节点合并,再将 $3$ 号节点与 $5$ 号节点合并。
注意到一个性质,合并的节点都在同一层(因为长度相同)。

接下来我们考虑如何求答案。
我们可以把合并信息下传:
比如:

          10[1, 4]   11[2, 5]
   6[1, 2] 7[2, 3]  8[3, 4] 9[4, 5]
1[1, 1] 2[2, 2] 3[3, 3] 4[4, 4] 5[5, 5]

我们把 $6$ 和 $8$ 合并了,我们就把 $1$ 和 $3$ 合并,且把 $2$ 和 $4$ 合并。这样就完成了下传。

最后注意,首位不能为 $0$。

代码

/*
 * Please submit with C++14! It's best to use C++20 or higher version.
 * By rbtree (https://rbtr.ee)
 * Apparition (n@rbtr.ee)
 * DO OR DIE
 */

#include <algorithm>
#include <cstdio>
#define AS 3 +

using namespace std;
using tp = long long;

constexpr tp Hat_N = 1e5, Hat_F = __lg(Hat_N), c_Mod = 1e9 + 7;

tp f[AS Hat_N][AS Hat_F];

tp find(tp x, tp l) { return f[x][l] == x ? x : f[x][l] = find(f[x][l], l); }

void link(tp x, tp y, tp k) { f[find(x, k)][k] = find(y, k); }

signed main() {
  tp n, m, fl, tar = 0;
  scanf("%lld%lld", &n, &m);
  fl = __lg(n);
  for (tp i = 1; i <= n; ++i) {
    for (tp j = 0; j <= fl; ++j) f[i][j] = i;
  }
  while (m--) {
    tp l1, r1, l2, r2;
    scanf("%lld%lld%lld%lld", &l1, &r1, &l2, &r2);
    for (tp i = fl; i >= 0; --i) {
      if (l1 + (1ll << i) - 1 <= r1) {
        link(l1, l2, i);
        l1 += 1ll << i;
        l2 += 1ll << i;
      }
    }
  }
  for (tp i = fl; i > 0; --i) {
    for (tp j = 1, endj = n + 1 - (1ll << i); j <= endj; ++j) {
      link(find(j, i), j, i - 1);
      link(find(j, i) + (1ll << i - 1), j + (1ll << i - 1), i - 1);
    }
  }
  for (tp i = 1; i <= n; ++i) {
    if (f[i][0] == i) tar = tar ? (tar * 10 % c_Mod) : 9;
  }
  printf("%lld\n", tar);
  return 0;
}

//*/

暂无评论

发表评论