QTREE 系列.
QTREE1
树剖维护即可,注意 LCA 连向它父亲的边不能被计入贡献.利用重链上 dfn 连续这条性质,就可以做到了.
时间复杂度 $O(n\log n)$ .
QTREE2
预处理出父亲的倍增数组,每个点的深度以及到根的距离.第一问找出 LCA 计算一下就可以了.
第二问可以从深度大的往上跳,如果跳到 LCA 还没结束,就换另一个点来跳.
跳的时候要记录跳过了几个点,更换跳的点的时候要处理 $k$ 的变化.
时间复杂度 $O(n\log n)$ .
QTREE3
把 dfn 看作下标,则这个询问等价于询问一段区间内的第 $k$ 大.
没有修改操作,把权值离散化后建出主席树来回答询问即可.
时间复杂度 $O(n\log n)$ .
QTREE4
和 捉迷藏 那题一模一样,可以用动态点分治来做,时间复杂度 $O(n\log^2 n)$ .
QTREE5
和 QTREE4 大同小异,其实可以看做是 QTREE4 的一个弱化版.仍然考虑动态点分治.
给每个分治中心开一个 set ,维护它管辖的所有白点到它的距离,以及它们的编号.
修改时在点分树跳,把经过的每个 set 的信息更新一下.
询问时在点分树上跳,不断用 set 中的最小值来更新最小距离.
这样会将一些自交的链也统计进去,但由于是询问 $\min$ ,不会影响答案正确性.
时间复杂度 $O(n\log^2 n)$ .
QTREE6
开两棵 LCT ,分别维护白点,黑点的信息,询问的答案就是 $u$ 所在的连通块大小.
这可以通过维护虚儿子的大小和得出.
修改时,需要将 $u$ 在某棵 LCT 中断掉,在另一棵 LCT 中加入,如果每次暴力修改,会被菊花图卡掉.
我们常常把边 $u\to v$ 的贡献放到点 $v$ 上来统计,这里可以将 $u$ 的信息放到边 $fa(u)\to u$ 上统计.
即,在白点的 LCT 中,若边 $fa(u)\to u$ 存在,说明 $u$ 为白色.这样修改时就只需要删一条边,加一条边了.
询问时,由于根节点的边 $fa(root)\to root$ 不存在,说明根的颜色与 $u$ 不同,它的所有儿子不能连起来.
于是还需要把根给去掉,在 findroot(u) 找到根后,把它 Splay 上来,它的右儿子就是 $u$ 所在的子树.
需要给原图加一个虚点,表示原图树根的父亲.
时间复杂度 $O(n\log n)$ .
QTREE7
和 QTREE6 大同小异,只是把连通块大小换成了连通块内点权最大值.
用 multiset 维护虚儿子贡献上来的最大值,其它部分同 QTREE6 .
时间复杂度 $O(n\log^2 n)$ .