原题链接（可能打不开）：https://www.luogu.com.cn/problem/T211214

时限 0.5s 自然是为了卡 log 做法。

$n\le 100$ 的数据

枚举所有区间，sort 排序，求中位数。复杂度 $O(n^3\log n)$。可以用插入排序或 nth_element 做到 $O(n^3)$。

$n\le 1000$ 的数据

先枚举区间左端点 $l$，考虑在枚举右端点的同时快速维护区间中位数。

这是一个经典问题，可以直接使用 pb_ds 的平衡树方便地解决，也可以使用 priority_queue。见 P3871，不展开。 $O(n^2\log n)$。

$\{a_n\}$ 为排列

考虑每个数字 $a_i$ 作为中位数的方案数 $f_i$，那么答案为 $\sum a_if_i$。令 $b_j=sgn(a_j-a_i)$（$sgn(x)$ 表示 $x$ 的正负情况。$sgn(-2)=-1,sgn(2)=1,sgn(0)=0$），若区间 $[l,r]$ 的中位数是 $a_i$，那么 $\sum\limits_{i=l}^rb_i$（记为 $g(l,r)$） 一定为 $-1$ 或 $0$。考虑对某个 $i$ 记录 $l_k=\sum\limits_{l\le i}[g(l,i)=k]$，$r_k=\sum\limits_{i\le r}[g(i,r)=k]$，那么 $f_i=\sum l_{k}r_{-k}+\sum l_kr_{-k-1}$。复杂度 $O(n^2)$。

$100\%$ 的数据

和排列不同的是，$\{1,2,2,3\}$ 可能在 $2$ 个 $2$ 处都计入了 $f$。考虑把数字看成二元组 $(a_i,i)$ 比较大小，即先比较数字后比较下标，这样就不会重复统计了。如果细节处理不慎可能只能得到排列的分数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
const int N=7010;
int a[N],s[N],cc[N*2],*cnt=cc+N;
int n,i,j,x,y,mid;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for (i=1;i<=n;i++) cin>>a[i];
	for (mid=1;mid<=n;mid++)
	{
		s[mid]=0;
		for (i=mid-1;i;i--) if (a[i]>=a[mid]) s[i]=s[i+1]+1; else s[i]=s[i+1]-1;
		for (i=mid+1;i<=n;i++) if (a[i]>a[mid]) s[i]=s[i-1]+1; else s[i]=s[i-1]-1;
		x=0;y=0;
		for (i=mid;i<=n;i++) x=min(x,-s[i]),y=max(y,-s[i]);
		x-=2;y+=2;
		for (i=x;i<=y;i++) cnt[i]=0;
		for (i=mid;i;i--) ++cnt[s[i]];
		for (i=mid;i<=n;i++) ans+=(ll)(cnt[-s[i]]+cnt[-s[i]-1])*a[mid];
	}
	cout<<ans<<endl;
}