20250718-FDU-HDUOJ钉耙编程一
前言
喜提倒一
正文
10. 中位数
题意
给出长 nnn 的排列 a1,a2,...,ana_1,a_2,...,a_na1,a2,...,an。求 ∑1≤l≤r≤n[(r−l)≡0mod2]⋅l⋅r⋅p(a[l,...,r])\sum_{1\le l\le r\le n}[(r-l)\equiv0\mod2]\cdot l\cdot r\cdot p(a[l,...,r])∑1≤l≤r≤n[(r−l)≡0mod2]⋅l⋅r⋅p(a[l,...,r])，其中 p(a)p(a)p(a) 表示序列 aaa 的中位数。
做法
听说 O(Tn2logn)O(Tn^2\log n)O(Tn2logn) 能卡常卡过去，但是没试成功，一个做法是对顶堆，另一个做法是树状数组上的倍增。需注意倍增只能求一定条件下的最大值，所以我们求不符合条件的最大值再加一。
正解是 O(Tn2)O(Tn^2)O(Tn2)。就是枚举中位数，然后其他数字中我们只关心它和中位数的相对大小，所以记比中位数小的为 −1-1−1，比中位数大的为 111，然后求其前缀和 sumsumsum，a[l,r]a[l,r]a[l,r] 成立当且仅当 suml−1=sumrsum_{l-1}=sum_rsuml−1=sumr。
代码
HUDOJ 提交记录
paste