T2题解
这篇TJ必定非常抽象，因为我现在并不会做
稍微说一下题意
给一个序列，求序列中所有子序列的中位数之和
若子序列长度为偶数，取中间两者的后者作为中位数，而非平均数
okokokok可以不会做了
躺
________________
/ 有些人， \
| 躺着躺着，就逝了。 |
---- | ________________/
/ x |\ |/
| | ______________............../|
\ / ===|_\ ___________.............,|
---- \----------]
起床啦～
首先，$n=7000,Timelimit=500ms$明摆着不能列出所有状态
我们若是用n方的复杂度枚举出所有区间，就只剩$O(1)$的复杂度找中位数了，这能做到么？
在下不才，这番折腾属实是为难小生了，恕罪
于是有一个常用的trick，我们考虑每个数作为中位数的贡献，显然（这够显然了），每个数能作为多少次中位数，就对答案贡献了几倍的自己。
于是，问题来到了——每个数能作为多少次中位数？
ok，枚举每个数作为中位数，我们已经耗了$O(n)$,手头还剩$O(n)$。
- 第一，暴力枚举包含这个中位数的所有区间，$O(n^2)$，炸透了。
- 第二，思考能不能双指针，但是却不单调，悲。
- 第三，我们想想到底什么样的区间可以让我们枚举的$a_i$作为中位数。
$$ cnt_{k \in [l,r]}(a_k<a_i)=cnt_{k \in [l,r]}(a_k>a_i) $$
首先，cnt不是数学量，略改一下
$$ \sum_{k=l}^{r} [a_k<a_i] = \sum_{k=l}^{r} [a_k>a_i] $$
其中$[<bool>]$函数指：
$$ [b] = \begin{cases} if(b==true)1 \\if(b==false)0 \end{cases} $$
然后把他们都拆成左右两部分，显然，$k=i$的那一项可以直接删
$$ \sum_{k=l}^{i-1} [a_k<a_i] + \sum_{k=i+1}^{r} [a_k<a_i] = \sum_{k=l}^{i-1} [a_k>a_i] + \sum_{k=i+1}^{r} [a_k>a_i] $$
ok现在移项：
$$ \sum_{k=l}^{i-1} [a_k<a_i] - \sum_{k=l}^{i-1} [a_k>a_i] = \sum_{k=i+1}^{r} [a_k>a_i] - \sum_{k=i+1}^{r} [a_k<a_i] $$
$$ \sum_{k=l}^{i-1} ([a_k<a_i] - [a_k>a_i]) = - \sum_{k=i+1}^{r} ( [a_k<a_i]-[a_k>a_i] ) $$
定义$sign(x)$函数：
$$ sign(x) = \begin{cases} if(x==true) 1 \\if(x==false)-1 \end{cases} $$
如果$\forall{k}, a_k \not = a_i$
那么显然
$$ \sum_{k=l}^{i-1} sign([a_k<a_i]) = - \sum_{k=i+1}^{r} sign([a_k<a_i]) $$
那推到这里，就可以向两边各做一个前缀和
在两个前缀和数组中，每遇到互为相反数的就会对答案贡献一次
定义：
$$ LeftSum_x = \sum_{k=i-x}^{i-1} sign([a_k<a_i]) $$
$$ RightSum_x = - \sum_{k=i+1}^{i+x} sign([a_k<a_i]) $$
这两个前缀和可以$O(1)$算
统计贡献，$a_i$作为中位数的贡献：
$$ ans_{a_i} = \sum_{x=1}^{i-1}\sum_{y=1}^{n-i}([LeftSum_x=RightSum_y] \times a_i) $$
$$ ans_{a_i} = a_i \times \sum_{x=1}^{i-1}\sum_{y=1}^{n-i}[LeftSum_x=RightSum_y] $$
这个$O(n^2)$是假的，因为式子随便推：
$$ ans_{a_i} = a_i \times \sum_{x=1}^{i-1}cnt_{y=1}^{n-i}(RightSum_y = LeftSum_x) $$
记$RightSum.cnt[x]$为$x$在$RightSum$出现的次数。
$$ ans_{a_i} = a_i \times \sum_{x=1}^{i-1}RightSum.cnt[LeftSum_x] $$
$RightSum.cnt$数组显然和可以预处理
于是到此为止已经是$O(n)$了，但你可以再推一步：
$$ ans_{a_i} = a_i \times \sum_{x=1}^{max(LeftSum,RightSum)}(LeftSum.cnt[x] \times RightSum.cnt[x]) $$
看到这一步是不是已经懵了（
要是你奇怪右边几乎和$i$没关系的时候
我只能提醒你一下两个前缀和数组要建立在$i$的基础上预处理而得
到这一步，基本完整的$O(n^2)$方法就做完了
其实回看方法，这个若通过感性理解，完全不需要推式子，毕竟乘法原理嘛