Luogu7126 [Ynoi2008] rdCcot

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

题意 : 给一棵 个点的树和常数 。

每次查询给出区间 ，查询有多少个 C-块，定义如下：

对任意两个节点 ，定义 是 C-连通的，当且仅当存在一个长为 的节点序列 ，满足：



  3. 对任意 ，
  4. 对任意 ，

定义“C-块”为一个点集 ，满足：

  1. 对任意 ， 属于 的补集， 不 C-连通
  2. 对任意 ， 和 C-连通
  3. 对任意 ，有

，，时限 。

  • Part1

不难发现 C-块 点集是不交的，且任意两个 C-块 的虚树也是不交的。

考虑在每个 C-块 的最浅点将其统计，若同样浅，则选择编号较小的。（注意不是虚树的最浅点）

我们按照这个规则定义点的大小关系。

先考虑静态问题。给出一个点集 求 C-块个数。

每个点向距离 以内的最小点连边（如果这个最小点比自己小的话）。可以发现，没有出边的点就是一个 C-块 的最小点。

  • 正确性说明：相当于要证：从点 不断跳向距离 以内的最小点，最终可以来到所在 C-块 的最小点。

    只有距离 以内没有更小的点才不能跳，因此上面的结论是显然的。

  • Part2

接下来考虑区间询问。

我们只需要快捷地判定某个点是否存在出边。

记距点 在 以内的，小于点 的，编号离 最接近的两个点分别为 ，一左一右。

对于点 ，若 且 ，则 没有出边，是某个 C-块 中的最小点。

考虑求出 之后如何回答询问。

使用扫描线，增大右端点并维护每个左端点的答案。

对子 当 增大到 时，开始将左端点 的答案均 。当 增大到 时，取消贡献。

树状数组即可。

  • Part3

考虑如何求出 。

使用点分治。对于点 ，记到分治中心的距离为 。

每个点 会询问来自其他分支的（这个不用管，一定更劣）， 比 小的，满足 的，编号最接近的 。

考虑静态问题。将点按照大小排序，逐个插入以点编号为下标的线段树，线段树内维护 的最小值。

查询时，只能走存在 的分支，在此基础上，尽量“向左”或“向右”走即可。

这容易用线段树维护。总复杂度 。