比较麻烦的二维数点.
随机生成数据带来的性质
首先需要注意数据的生成方式是给出的,表面上是减少输入量,实际上蕴含了这棵树的一些有用的性质.
前 $p$ 个点形成一条主链,后面的点随机向前面的点连边,那么每个点到主链的距离期望是 $O(\log n)$ 的.
于是对于树上任意两个点 $x,y$ 和它们的最近公共祖先 $l$ , $\min(dis(x,l),dis(y,l))$ 的期望也是 $O(\log n)$ 的.
此外,由于每个点颜色是在 $[1,n]$ 中随机的,所以在期望意义下,每种颜色只会有 $O(1)$ 个点.
第一问
先考虑第一问怎么做,求区间内颜色数目通常可以找出 $p_i$ 表示上一个和 $i$ 颜色相同的点,然后二维数点.
现在是在树上,就令 $p_i$ 表示 $i$ 的所有真祖先中,颜色与 $i$ 相同且深度最大的点.
不妨令 $dis(x,l) <dis(y,l)$ ,我们可以先求出 $[l, y]$ 这条链上的颜色数目,这可以用主席树二维数点 $O(\log n)$ 求出.
再枚举 $(l,x]$ 链上的每个点 $i$ ,若 $i$ 的颜色是 $c$ ,就找出所有颜色是 $c$ 的点,如果都没有在 $[l,y]$ 上出现, $i$ 就有贡献 $1$.
检查某个点是否在 $[l,y]$ 这条链上可以直接用欧拉序判断.
$(l,x]$ 这条链上期望只会有 $O(\log n)$ 个点,而每个点期望只会有 $O(1)$ 个点和它颜色相同,每次判断也是 $O(1)$ 的.
于是单次第一种询问的时间复杂度为 $O(\log n)$ .
第二问
仍然令 $dis(x,l) <dis(y,l)$ ,可以讨论 $a,b$ 所在的位置,拆成三个子问题.
Case 1
$a\in [1,l), b\in [1,y]$ .这等价于在一条链上询问,点 $i$ 能产生贡献,当且仅当 $L\in[p_i+1,i], R\ge i$ .
于是可以对 $i$ 分段,将贡献大力拆开,用主席树维护一下区间的 $\sum 1, \sum i,\sum p_i,\sum i\cdot p_i$ 就可以支持询问.
Case 2
$a\in [l,x],b\in[1,l)$ .我们把 $a\in [1,x],b\in[1,l) $ 的贡献算出来,再减去 $a\in [1,l),b\in[1,l) $ 的贡献.
这两种贡献和 Case 1 的形式是一样的.
Case 3
$a\in [l,x],b\in[l,y]$ .先计算 $[l,y]$ 上的点的贡献,此时不考虑 $[l,x]$ 内的点的颜色,贡献拆开后就是一个二维数点.
再考虑 $[l,x]$ 上的每个点 $i$ ,它有贡献当且仅当 $p_i<l$ 且 $[l,b]$ 内没有和它颜色相同的点.
找出 $q_i$ 表示 $[l,y]$ 中第一个和 $i$ 颜色相同的点(没有就记作 $y+1$ ).
当 $p_i<l$ 时,就有贡献 $(x-i+1)(q_i-l)$ ,仍然可以用二维数点计算.
每种情况都可以在 $O(\log n)$ 的时间内求出贡献,总复杂度 $O(n \log n)$ .
1 | //%std |