【学习笔记】可持久化并查集（BZOJ3673）

可持久化并查集是指在并查集基础上，新增了时间维度，即支持查询历史版本的并查集信息。

主要应用场景是需要记录数据变化历史的问题，比如线段树合并、动态图连通性等。

以下是实现可持久化并查集的基本思路：

1. 每个节点维护一个 father 数组，表示该节点的祖先节点

2. 对于每个版本，使用一个 map（键值对）来记录每个节点的祖先节点

3. 合并操作时，将两个节点的祖先节点找出来，若不同就将其中一个节点的祖先节点指向另一个节点的祖先节点

4. 查询操作时，查询对应版本的 map，返回节点的祖先节点

具体实现时，可以使用并查集路径压缩和按秩合并优化，以提高效率。

以下是代码实现（C++）：

相关问题

bzoj2908数据下载

BZOJ 2908 题目是一个数据下载任务。这个任务要求下载指定的数据文件，并统计文件中小于等于给定整数的数字个数。

为了完成这个任务，首先需要选择一个合适的网址来下载文件。我们可以使用一个网络爬虫库，如Python中的Requests库，来帮助我们完成文件下载的操作。

首先，我们需要使用Requests库中的get()方法来访问目标网址，并将目标文件下载到我们的本地计算机中。可以使用以下代码实现文件下载：

import requests

url = '目标文件的网址'
response = requests.get(url)
with open('本地保存文件的路径', 'wb') as file:
    file.write(response.content)

下载完成后，我们可以使用Python内置的open()函数打开已下载的文件，并按行读取文件内容。可以使用以下代码实现文件内容读取：

count = 0
with open('本地保存文件的路径', 'r') as file:
    for line in file:
        # 在这里实现对每一行数据的判断
        # 如果小于等于给定整数，count 加 1
        # 否则，不进行任何操作

在每一行的处理过程中，我们可以使用split()方法将一行数据分割成多个字符串，并使用int()函数将其转换为整数。然后，我们可以将该整数与给定整数进行比较，以判断是否小于等于给定整数。

最后，我们可以将统计结果打印出来，以满足题目的要求。

综上所述，以上是关于解决 BZOJ 2908 数据下载任务的简要步骤和代码实现。 希望对您有所帮助。

BZOJ2627 伯努利数

这是一道经典的组合数学题目，需要一些基本的组合数学知识。

首先，我们先来了解一下伯努利数。伯努利数是组合数学中的一类数列，它们的递推式如下：

$$B_0 = 1, B_n = -\frac{1}{n+1}\sum_{i=0}^{n-1}{{n+1}\choose{i}}B_i$$

其中 $n\geq 1$，${n\choose k}$ 表示组合数，$B_n$ 表示第 $n$ 个伯努利数。

接下来，我们考虑如何计算 $\sum_{i=0}^{n}{n+1\choose{i}}B_i$。根据二项式定理，我们有：

$$(1+x)^{n+1} = \sum_{i=0}^{n+1}{n+1\choose{i}}x^i$$

对上式两边求导可以得到：

$$(n+1)(1+x)^n = \sum_{i=1}^{n+1}{n+1\choose{i}}ix^{i-1}$$

将 $x=1$ 带入上式，得到：

$$(n+1)\cdot 2^n = \sum_{i=1}^{n+1}{n+1\choose{i}}i$$

注意到 $B_0=1$，我们可以对伯努利数的递推式进行变形：

\begin{aligned} B_n &= -\frac{1}{n+1}\sum_{i=0}^{n-1}{{n+1}\choose{i}}B_i \\ &= -\frac{1}{n+1}\left({{n+1}\choose{0}}B_0 + \sum_{i=1}^{n}{{n+1}\choose{i}}B_i\right) \\ &= -\frac{1}{n+1}\left({{n+1}\choose{0}}B_0 + \sum_{i=1}^{n}{n+1\choose{i}}B_i\right) + \frac{1}{n+1}{{n+1}\choose{0}}B_0 \\ &= -\frac{1}{n+1}\sum_{i=0}^{n}{n+1\choose{i}}B_i + \frac{1}{n+1} \end{aligned}

因此，我们有：

$$\sum_{i=0}^{n}{n+1\choose{i}}B_i = (n+1)(B_{n+1}-1)$$

这个式子可以通过数学归纳法进行证明。

现在，我们已经得到了 $\sum_{i=0}^{n}{n+1\choose{i}}B_i$ 的计算公式，只需要预处理出前 $n$ 个伯努利数就可以在 $O(n)$ 的时间复杂度内解决这个问题了。