事实上也可以这样：记录 $pre_c$ 表示 $c$ 最后一次出现的位置。扫描线，扫到询问 $(l, r, c)$ 的时候只需判断是否有 $pre_c\ge l$ 即可。
这样的复杂度仍然是 $\mathcal O(m\log n)$。

本人做法:树链剖分+主席树 $O(nlog^2n)$
还有其他做法:
·树剖+线段树+平衡树(树套树套树? Orz) $O(nlog^3n)$
·dfs+主席树 $O(nlogn)$
·树剖+分块 $O(n\sqrt{n}log(n\sqrt{n}))$
都不会捏┭┮﹏┭┮

写完此题受益良多啊，在这里写个小总结吧。。。
1.算是复习了一边树剖（是的我没写主席树，这就是吸氧也不如一只log的主席树快的原因。。。）虽然在跳链时写错了一点。。。
2.学到了新的判断数是否在区间的方法。。
3.使用了毒瘤的新码风。。
4.对迭代器有了较浅的理解。。
5.%%%%%%%%%hs大佬