合并序列

显然代价随着增加是递减的，于是我们可以二分。

对于给定的怎么计算答案呢？这是一个经典的哈夫曼树问题。

首先，我们先补一定个数的0。使得 n mod (k - 1) = 1。

然后每次合并最小的个即可。

我们维护一个队列，每次合并后把新产生的数扔里，然后选最小

的个时就在原数列和里选，因为显然也是单调不增的。

于是我们只需要排序预处理就可以了。

Minmax

因为区间的交还是一个区间，所以我们考虑枚举最终区间的交[L,R]。

然后统计li <= L且R <= ri的区间个数，令为tot个；

则将min(R-L+1, tot)去更新答案。

优化这个过程，我们可以只枚举右端点R，然后考虑对于每一个左端点L(L <= R)，

维护出有多少区间包含[L,R]，记为f(L)。

容易发现当R固定时，随着L增加，R-L+1是一个减函数，而f(L)是一个增函数。

所以min(R-L+1, f(L))的最大值，必然是取到这两个函数最接近的时候最优。

朴素的想法，我们可以二分L，找到最小的一个L，满足R-L+1 <= f(L)，然后取L-1,L的信息去更新答案。

因为线段树本质也是一个分治结构的形态，所以对于二分答案的题，是可以直接在线段树上二分的。

具体来说，我们令T(L) = R-L+1 - f(L)，这样T(L)是一个减函数，我们直接在线段树上二分找到对应的L即可。

当R增加的时候，我们时时维护一下线段树即可，需要支持区间加，区间询问最小值。

子序列

考虑计算每种子序列是否出现，为了避免重复计算，我们都只算第一个出现的。

令f[i]表示末尾为i的子序列的期望出现个数，枚举这个子序列下一个字符c。

然后枚举后面所有字符是c的位置x，那么f[i]转移到f[x]的概率就是，[i+1..x-1]中所有等于c的位置被删除的概率*第x个位置不被删的概率。

前缀和转移即可。

chess

打个表易得：

1. min(n,m)=1的时候答案为1。

2. Min(n,m)=2的时候答案为max(n,m)/2。

3. 否则答案为n*m。

4. 坑点在n = 3, m = 3 的时候答案是8。

5. 证明见https://apps.topcoder.com/wiki/display/tc/SRM+564

Tree

这道题要涉及求(ai,aj)以及(bi,bj)的距离，这两个变量还不好隔离；所以我们考虑先用点分将来简化一对，不妨考虑枚举(ai,aj)越过的重心，令Dep(x)表示x到重心的距离，则i,j之间的权值就变成了： Dep(ai) + Dep(aj) + Dis(bi, bj) 此时(i,j)之间相关的权值只和Dis(bi,bj)有关，剩下的是可以视为i,j的点权的，不影响答案。 接下来有两种方法。 第一种，我们可以再建立一棵点分树，每次合并时，就拿bj去点分树上询问一下权值最大的bi；然后将bj加入点分树即可。注意每次询问时，要求bi和bj在不同的分支上，所以我们需要对点分树上的每一个节点，记录两个属于不同的分支的最大值。 效率为：O(N \log^2 N)。 还有一种方法，我们发现将Dis(ai,aj)分离后，我们本质就是要求点集中带点权的直径；因为我们可以将Dep(ai)视为是bi点的点权。对于一个点集，实现加点后动态枚举直径，是有一个性质的；即距离一个点距离最远的点，必然是直径的两个端点，这个性质在带点权的时候同样正确。 所以我们是不需要用点分树来维护直径的；直接维护出直径的两个端点，每次加入点后，去直径询问一下，并更新即可。把LCA可以写成O(1)的，效率为O(N \log N)。