【题解】HackerRank-Coloring Tree

题目

https://www.hackerrank.com/challenges/coloring-tree/problem

题意

询问子树结点中的出现过的颜色总数。

题解

  • dfs 序,转化为数列上的区间询问问题。
  • 莫队无脑搞一搞。

代码

1
2


另解

  • 询问 [l, r] 也就是考虑 [1, r] 中每个颜色最后的出现位置,有多少在 [l, r] 中。
  • 依次考虑数列中的每个数(当前考虑到第 k 个数),维护每个位置是否是该颜色最后一次出现,回答 r=k 的所有询问。
  • 复杂度:相比起用莫队的 \(O(n^{1.5})\),这种解法 \(O(n\log n)\)