http://codeforces.com/contest/341
赛后做的虚拟比赛，40分钟出了3题，RP爆发。
A计数问题
我们可以对每对分析，分别对每对<a, b>(a走到b)进行统计，那么这对<a, b>产生的期望为distance(a, b)/n
(把这一对选出来以后相当于一个点，那么分子distance(a, b)*(n-1)!,分母n!, (n-1)被约掉了。)
这样的算法是O(n^2)的，问题转化为统计所有对<a, b> 的距离。我们可以对输入的a数组排序
那么对于每对<a,b>可以拆成几段相邻a数组的值之差。
对于零到其它点另外拿出来考虑，显然ans += 所有a数组的值，
没有零的情况，枚举相邻a数组的值,然后统计经过这两个点的<a,b>对数(注意方向有两种，要乘以2)。
看上去很多，但有了思路就很快的。
B最长不下降序列O(n*log(n) )
找找规律可以发现，对于每个数，它后面有比它小的数，那么它们就有一条边，我们找独立点集是找没边的，
所以对于一个数，在它后面的数我们只能选择大于等于它的数。
C裸的容斥
《组合数学》里面容斥那章有很多类似的题目，记得某次浙大月赛也出过类似的题，这种题已经做烂了。
D二维树状数组
赛后补的题，比赛的时候想用线段树做，但二维线段树空间开不下， 一维是可以做的。
我们先分析一维树状数组的做法，树状数组是向后更新向前查询的，
对于(1---n)，我们先假设更新都是(x---n)， 查询都是(1---x)，其它情况可以分成2个更新或2个查询。
更新 xor v:若x为奇数，那么我们要查询x+1，x+3.....时这个v值是没有用的(抑或掉了)。 有用的是x+2,x+4....
若x为偶数，反之亦然。
很显然我们开两个树状数组，分别是奇数位置和偶数位置。
查询: 若x为奇数，查询奇数的树状数组
若x为偶数，查询偶数的树状数组
推广到二维也是一样的。