题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5701
题目：
题目分析：这题显然满足条件的区间必是含奇数个数的区间，对于每个数，先往右扫一遍，求得其右边比其大的和比其小的数的个数的差x，然后再往左扫一遍，求其左边比起小的数和比起大的数的差，若一个数在这个区间为中位数，则若其右边比它大的比比它小的多x(有点绕)，则其左边相反小的要比大的多x，这样x才能正好在中间位置，用一个数组记录一下差值为某个数的个数即可，注意要算上这个数自己。
注意：输入的n个数，是无序数列，这里也不能对其进行排序后再判断。
原文：https://blog.csdn.net/tc_to_top/article/details/51477047
/* HDU5701 中位数计数 */ #include <iostream> #include <cstring> using namespace std; const int MAXN = 8000; int v[MAXN+1], count[2*(MAXN+1)]; int main() { int n, ans, cnt; while(cin >> n) { for(int i=1; i<=n; i++) cin >> v[i]; for(int i=1; i<=n; i++) { memset(count, 0, sizeof(count)); cnt = 0; count[n]++; for(int j=1; j<i; j++) { if(v[i - j] < v[i]) cnt--; else cnt++; count[n + cnt]++; } cnt = 0; ans = count[n]; for(int j=1; i+j<=n; j++) { if(v[i+j] < v[i]) cnt--; else cnt++; ans += count[n - cnt]; } if(i==n) cout << ans << endl; else cout << ans << " "; } } return 0; }
原文：https://www.cnblogs.com/LJHAHA/p/10532878.html