#P18514. Random Permutation
Random Permutation
Random Permutation
小青鱼正在参加 B 教授开设的算法竞赛网络课程“Big-God-Live-Class”。最近的一节课上,B 教授介绍了使用两个优先队列维护序列中位数的技巧。小青鱼决定实现这个方法来练习。
具体地,他的程序会从输入文件读取一个长度为 (n) 的排列 (p_1,p_2,\ldots,p_n),并计算它的所有非空连续子数组的中位数之和: [ \sum_{1\le l\le r\le n}\operatorname{median}(p_l,p_{l+1},\ldots,p_r). ]
为了测试程序,小青鱼希望均匀随机生成一个 (1,2,\ldots,n) 的排列,计算正确答案,再与自己的程序输出比较。请你帮他求出这个正确答案。
长度为 (t) 的序列的中位数是将元素从小到大排序后,第 [ \left\lceil\frac t2\right\rceil ] 小的数,即偶数长度时取两个中间数中较小的那个。例如,([1,5,4]) 的中位数是 (4),([11,4,5,14]) 的中位数是 (5)。
输入格式
第一行包含一个整数 (n)((1\le n\le3\times10^5))。
第二行包含 (n) 个整数 (p_1,p_2,\ldots,p_n)((1\le p_i\le n)),它们构成一个排列。
保证 (p) 是由伪随机数生成器从全部 (n!) 个排列中均匀选取得到的。
本题最多有 20 个测试文件,每个输入文件仅包含上述一组测试。
输出格式
输出一行一个整数,表示所有非空连续子数组的中位数之和。
样例
输入:
4
1 4 2 3
输出:
22
这十个连续子数组的中位数分别为:
| 子数组 | 中位数 |
|---|---|
| ([p_1]=[1]) | 1 |
| ([p_2]=[4]) | 4 |
| ([p_3]=[2]) | 2 |
| ([p_4]=[3]) | 3 |
| ([p_1,p_2]=[1,4]) | 1 |
| ([p_2,p_3]=[4,2]) | 2 |
| ([p_3,p_4]=[2,3]) | |
| ([p_1,p_2,p_3]=[1,4,2]) | |
| ([p_2,p_3,p_4]=[4,2,3]) | 3 |
| ([p_1,p_2,p_3,p_4]=[1,4,2,3]) | 2 |
因此答案为 (1+4+2+3+1+2+2+2+3+2=22)。
中位数说明
长度为 的子数组取第 小的元素;偶数长度取两个中间值中较小的一个。