解题思路

本题是要求区间内不同数的个数，这是主席树的常见应用之一了。

做法很简单，我们可以倒序（从右向左）建立主席树，如果一个值还没出现过，则直接插入，否则删除后再重新插入（相当于保留这个数最左出现的位置）。之后要查询 [l, r] 时，选用 l 位置的主席树，这时树中的数据是 [l, n] 范围内的，因此查询时需要传入 r 作为挡板，仅统计小于等于 r 的个数，这样就可以实现 [l, r] 区间不同数的查询。

当然也可以保留每个数最右出现的位置来正序建树，和上面的做法就反过来了。

解题思路

主席树的区间第 K 大的树上版本。

从根结点到每个结点都建立一个版本的线段树即可。查询时 a 到 b 路径时需要按照 $root[a] + root[b] - root[lca(a,b)] - root[fa[lca(a,b)]]$ 计算。

解题思路

题目要求查询区间内小于等于 H 的数的个数。很显然的主席树，建树之后直接在目标区间的主席树内将 H 作为挡板递归计数即可。

另外此题还可以用离线树状数组求解。

解题思路

本题概括起来有两种操作：

1. 更新路径上点权
2. 查询点权

树链剖分之后用线段树处理区间更新和单点查询即可（用树状数组应该会更简单一些）。

解题思路

本题只有两种操作：求树上两点间路径的权值和、修改边权。

于是使用树链剖分就很简单了。