「BZOJ1303」[CQOI2009] 中位数图（中位数）

本文主要是介绍「BZOJ1303」[CQOI2009] 中位数图（中位数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
Input
第一行为两个正整数n和b ，第二行为1~n 的排列。
Output
输出一个整数，即中位数为b的连续子序列个数。
Sample Input
7 4
5 7 2 4 3 1 6
Sample Output
4
Hint
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000
Source

思路： 我们只需要考虑其他数字与中位数的大小关系，那么更大的赋值为1，更小的赋为-1.跑前缀和和后缀和就可以了。用了map的写法，貌似常数很大···

ACNEW

#include <cstdio>using namespace std;int sum[200005],l[200005],r[200005],a[100005];
int main()
{int n,b;scanf("%d%d",&n,&b);int pos = 1;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);if(a[i] > b)a[i] = 1;else if(a[i] < b)a[i] = -1;else {a[i] = 0;pos = i;}}l[n] = 1;r[n] = 1;int ans = 0;for(int i = pos - 1;i >= 1;i--){sum[i] = sum[i + 1] + a[i];l[sum[i] + n]++;}for(int i = pos + 1;i <= n;i++){sum[i] = sum[i - 1] +a[i];r[sum[i] + n]++;}for(int i = 1;i < 2 * n;i++)ans += l[i] * r[2 * n - i];printf("%d\n",ans);return 0;
}

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;map<int,int>mpl1,mpl2,mpr1,mpr2;
int a[100005];int main()
{int n,b;scanf("%d%d",&n,&b);int pos = 1;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);if(a[i] > b)a[i] = 1;else if(a[i] < b)a[i] = -1;else{pos = i;a[i] = 0;}}int ans = 1;int tmp = 0;for(int i = pos + 1;i <= n;i++){tmp += a[i];if((i - pos) & 1){mpr1[tmp]++;}else{mpr2[tmp]++;}}tmp = 0;for(int i = pos - 1;i >= 1;i--){tmp += a[i];if((pos - i) & 1){mpl1[tmp]++;}else{mpl2[tmp]++;}}ans += mpl1[0] * mpr1[0] + mpl1[0] + mpr1[0];ans += mpl2[0] * mpr2[0] + mpl2[0] + mpr2[0];for(int i = 1;i <= n;i++){ans += mpl1[i] * mpr1[-i];ans += mpl1[-i] * mpr1[i];ans += mpl2[i] * mpr2[-i];ans += mpl2[-i] * mpr2[i];}printf("%d\n",ans);
}