对于一个长度为 (为奇数) 的数组 定义它的中位数 () 为 中第 12 大的数。现在给你一个长度为 的排列对于每对满足 1≤≤≤ 且 −≡0(2) 的 (,)你需要计算 ∗∗([,])。输出所有值的和。多测数 ≤20排列长度 ≤2000。对于这道题首先想到的是枚举所有 [,]通过数据结构(对顶堆等)维护中位数。由于这些方法都带log并且本题多测数据不保证 的总和。因此复杂度 (2)无法通过本题。换个思路枚举区间不行就计算每个位置的贡献。想想一个位置能成为一个区间的中位数需要满足什么条件该区间中大于它和小于它的数的数量相等。一个很经典的处理就是将小于 的数赋-1将大于 的数赋1我们对这个数组做前缀和记作 。于是问题就转换为在 的左边找到 在 的右边找到 使得 。那么 −0这就意味着区间 [1,] 中大于 和小于 的数的数量相等。对于每个数处理一次这样的前缀和数组是 () 的因此可以在 (2) 的时间下通过本题。Code:cpp#include iostream #include vector using namespace std; using ll long long; void solve() { int n; cin n; vectorint a(n10); for (int i 1 ; i n ; i) cin a[i]; ll ans 0; for (int i 1 ; i n ; i) //枚举中位数 { vectorint pre(n10); vectorint t(2*n10); //桶,因为会出现负数要带n的偏移 t[n]; for (int j 1 ; j n ; j) { pre[j] pre[j-1]; if (a[j] a[i]) pre[j]; else if (a[j] a[i]) pre[j]--; if (j i) t[pre[j]n] j 1; else ans (ll)a[i] * t[pre[j]n] * j; } } cout ans endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin T; while (T--) solve(); return 0; }基于本题可以归纳一个维护中位数的小技巧通过给大于 和 小于 的数分别赋值并求前缀和就可以把求中位数问题转化成维护前缀和之差为0。以下再做个拓展序列 的中位数 ()≥当且仅当 中 ≥≥式中是否取等号取决于题目怎么定义中位数。也就是说()≥ 的充要条件是 中 ≥ 的数的数量多于或等于 的数的数量。这个式子比较好理解这里不做证明。这个式子给我们提供了一种二分的思路。看下面这道题Submedians (Easy Version)对于长度为 的数组 整数 是 的中位数当且仅当 至少大于等于数组中 ⌈2⌉ 个元素并且 至少小于等于数组中 ⌈2⌉ 个元素。现在给定一个整数 和一个由 1 到 之间的整数构成的数组 1,…,。如果存在至少一对下标 (,) 满足1≤≤≤−1≥ 是子数组 [,…,] 的中位数则称 1 到 之间的整数 是一个子中位数。可以证明至少存在一个子中位数。请你找出最大的子中位数 max以及任意一组对应的下标对 (,)。考虑二分当 越大≥ 越少反之 越大因此越大的数越不可能作为中位数。同样将 ≥ 的数赋1 的数赋-1做前缀和维护即可。Code:cpp#include iostream #include vector using namespace std; void solve() { int n,k; cin n k; vectorint a(n10); for (int i 1 ; i n ; i) cin a[i]; int ansl, ansr; auto check [](int mid) { vectorint sum(n10); for (int i 1 ; i n ; i) { sum[i] sum[i-1]; if (a[i] mid) sum[i]; else sum[i]--; } int minn 2e9; int l; for (int i k ; i n ; i) { if (sum[i-k] minn) { minn sum[i-k]; l i - k 1; } if (sum[i]-minn 0) { ansl l; ansr i; return true; } } return false; }; int l 0; int r n 1; while (l1 ! r) { int mid (lr) 1; if (check(mid)) l mid; else r mid; } check(l); cout l ansl ansr endl; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin T; while (T--) solve(); return 0; }一道与上题几乎一样的题目Max Median题目很短这里不做题意概述。需要注意的是由于本题定义中位数为第 ⌊12⌋ 大的数因此本题 ()≥ 的条件为≥。Code:cpp#include iostream #include vector using namespace std; void solve() { int n,k; cin n k; vectorint a(n10); for (int i 1 ; i n ; i) cin a[i]; int ansl, ansr; auto check [](int mid) { vectorint sum(n10); for (int i 1 ; i n ; i) { sum[i] sum[i-1]; if (a[i] mid) sum[i]; else sum[i]--; } int minn 2e9; int l; for (int i k ; i n ; i) { if (sum[i-k] minn) { minn sum[i-k]; l i - k 1; } if (sum[i]-minn 0) { ansl l; ansr i; return true; } } return false; };