(x_i)在实数区间([a_i,a_i+m])内等概率随机。
对于每个(k)，问第(k)小期望是多少。
(nle 2000)
设(f_i(x))表示第(i)个大于(x)的概率。显然(ans_i=int f_i(x))。
可以得到(f_i(x)=[y^{i-1}]prod_j (P(x_j<x)y+1-P(x_j<x)))。其中(P(x_j<x))是关于(x)的函数，表示(x_j<x)的概率，是一个分段函数。
枚举每个极小段暴力计算，于是可以得到(O(n^4))的做法；由于相邻段之间的变化不会太多，用乘除一个短多项式来搞，于是可以得到(O(n^3))。
进一步搞。设(g_i(x))表示有至少(i-1)个数小于(x)的概率。如果算出(g_i)可以容斥得到(f_i)。现在有(g_i(x)=[y^{i-1}]prod(P(x_j<x)y+1))。
设(G(x)=prod(P(x_j<x)+1))。考虑到高阶求导的过程，相当于选择一些因式对其求导，然后加起来。在这题中，把常数的因式去掉，那么对某个因式求导是(frac{1}{m})。于是(g_i(x))就相当于(G(x))的高阶导数乘某个系数。
现在要对每个关键点求(int g_i(x))。于是可以先枚举关键点，再把(G(x))的高阶导数贡献到每一个(g_i(x))。(G(x))可以通过上一个区间的(G(x))乘除一些短多项式得到，求高阶倒数的贡献写出来是个卷积。于是时间(O(n^2lg n))。
没写。