题意概括
有若干集合，每个集合最初包含一个值，和一个编号1~n。两个操作：合并两个集合，查询包含值x的集合中第k大值最初的集合编号。
维护集合之间关系显然用并查集，但怎么处理询问，如果只是问最大值，那么显然可以用线段树把最大值存在并查集的祖先上，当然线段树也行。但这里问的是第k大。主席树？主席树是用来处理区间第k大的，而这里每棵树显然储存一整个集合（由多个小集合合并来的）的信息，我们并不关心这个集合内的区间问题，主席树便有点大材小用。所以，得出结论：用并查集和值域（权值）线段树合并。
你的线段树本来就能合并，那并查集是干嘛的呢？我们每次合并是取出x集合和y集合对应的A树和B树，并将B树的信息放到A上，就像这样：A B=>A+B B 如果是 A B=>A+B A+B或A B C(=A+B) 空间势必会炸。若不用并查集我们在查询集合y时，可能拿到的rt[y]树y的根就可能是 A B=>A+B B 中的那个B的而不是A+B的。用了并查集先把 f[y]=x 这样 rt[f[y] 就是 A+B 的根了。（不知不觉写了好多）
其实实现很简单，但对于不熟悉值域线段树和线段树合并的人就不容易了。
先放这道题里涉及值域线段树的代码（代码总是比人话好理解）：
AC代码
后来发现这道题还有更优的平衡树解法，但这个做法应该是码量最少的了，这也说明了值域线段树可以实现一些普通平衡树的操作，但不能完全替代。
Original: https://www.cnblogs.com/29taorz/p/15373997.html
Author: T_X蒻
Title: P3224 [HNOI2012]永无乡 题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/643459/
转载文章受原作者版权保护。转载请注明原作者出处！