给定长度为 \(n\) 的字符串 \(S\) 以及 \(m\) 个区间 \([l_i, r_i]\)，记 \(T=S[l_1,r_1]+\cdots+S[l_m,r_m]\)，其中 \(S[x,y]\) 表示从第 \(x\) 个字符到第 \(y\) 个字符的子串。求如何重新排列 \(S\) 中字符的顺序使得 \(T\) 的字典序尽可能大。
期望复杂度： 近似 \(O(n)\)。
czy's trick
在 \(S\) 中的每个位置有一个重要度，例如位置 \(l_1\) 是最重要的，应当放 \(S\) 中最大的字符，其次是 \(l_1+1,\dots,r_1,l_2,\dots\) 这些位置，且区间重复的部分以第一次出现为准。
相当于原问题变为了一个区间覆盖问题，我们只要以较快的速度跳过已经覆盖的区间即可。我们可以使用并查集维护区间，每个点对应并查集中的元素，在并查集合并的时候总是以较大的数作为父亲，则一个点的代表元就是其所在区间的右端点。
结合计数排序即可做到 \(O(n\alpha(n))\) 的时间复杂度。
例题：
标签：dots,并查,复杂度,查集,区间,维护,个字符 From： https://www.cnblogs.com/szdytom/p/how-did-we-get-here-3.html