Luogu5064 [Ynoi2014] 等这场战争结束之后

发表于 更新于 分类于 ， ， 阅读次数：

题意：维护一张 个点的无向图，点有点权，初始时没有边。

支持下列操作：

  • 添加一条 与 之间的无向边。

  • 回到第 次操作后的状态（注意这里的 可以是 ，即回到初始状态）。

  • 查询 所在联通块能到的点中点权第 小的值，如果不存在，那么输出 。

允许离线，，时限 ，空限 。

一切不强制在线的可持久化都是纸老虎！只需要建立操作树，就能把回档转化为撤回。

考虑值域分块，记块大小为 。对于每个询问，我们只需先判定答案在那个值域块内，再枚举块内的数进行检验。

对于每个值域块，将在块内的数的点权设为 ，不在块内的数的点权设为 。

对操作树进行 dfs，用可撤回并查集进行维护，容易查询联通块内的点权和。

这部分复杂度为 。

在得知答案所在值域块后，枚举块内的每个值大力判连通性即可。

这部分复杂度为 。

取 可得最优复杂度为 。

我们每次只处理一个值域块太浪费，考虑每次处理 个值域块，则复杂度改进为 ，取 即可做到 。（但空间需要 ）

已经可以通过。

将操作树分块，在树上撒 个关键点点使得每个点向上跳 次都会经过某个关键点。

对于每个关键点，不难 搜索得到此时的联通信息。

对于每个询问，只需从最近的祖先关键点向下加入 个修改然后搜索。

复杂度改进为 。

由于数据比较奇怪，块大小要开大一些。