• Projection

首先将a排序。那么显然b_i<=b_{i+1}。更多的，我们可以得到，存在l,r使得
1. 对于i < l，b_i=L。
2. 对于 i> r，b_i=R。
3. 对于l <= i <=r，a_i-b_i为常数。

并且，固定r，最优的l可以确定。我们对每个可能的r在O(logn)时间内求出最优的l即可。

可能存在某种形式的单调性，能进一步降低复杂度，不过题目设计为O(nlogn)可以通过所有数据。

• K个串

keywords: 可持久化线段树，堆

我们对于每个位置i，维护以它为左端点的所有子串的和（注意这里的和均为重复的数字只统计一次），并令c[i]为其为左端点的子串和的最大值。
对于全局最大的和，显然它是所有c[i]的最大值，不妨设为是c[j]，这时我们用j为左端点的所有子串中的次大值来更新c[j]。
以上过程重复k次即可找出k大值。
下面考虑如何维护c[i]。首先，我们令b[i]为[1, i]之间所有和，并以b[i]建立一棵线段树T。然后，我们发现，以2为右端点的子串所构成的线段树，就是T将[2, next[1])区间内所有数减ai，T中1位置赋为-inf的线段树，同理3，4...n为左端点的线段树，都可以由上一个修改而来。
于是，可以使用可持久化线段树来维护他们，同时，删除最大值和查询最大值也可轻松实现。而所有c[i]的最大值，使用一个堆来维护就可以了。
总的时间复杂度为O((n+k)lgn)

• Random Tree

首先固定A和B(要求期望的两个点)。考虑三类边：1. 两个端点是A或B 2. 一个端点是A或B 3. 没有端点是A或B

第一类边被取的概率是2/n。每个第二类边被取的概率是(1-2/n)/(n-2)。考虑第三类边，我们枚举A和B间边的个数k。令P(k)为A到B间边的个数为k的概率。那么期望的第三类边被取的个数是sum((k-2)*P(k))。P(k)可以通过考虑一个大小为(k+1)的连通块和n-k-1个大小为1的连通块的生成树个数求出。