欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1303
题意概括
给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
题解
我们找到b的位置，比如为pos。
然后往左，逐位统计比b小的，比b大的，差记为a。
对于左边所有的位置，bar[a]++，搞 n × 2 个桶。然后右边一边扫过去，一边根据桶的记录统计即可。
代码
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
typedef long long LL;
const int N=100000+5;
int n,k,pos,a[N],zero=N-5,bar[N*2];
int main(){
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
if (a[i]==k)
pos=i;
}
memset(bar,0,sizeof bar);
LL ans=1;
for (int i=pos-1,cnt=0;i>=1;i--){
if (a[i]<k)
cnt++;
else
cnt--;
bar[cnt+zero]++;
if (cnt==0)
ans++;
}
for (int i=pos+1,cnt=0;i<=n;i++){
if (a[i]<k)
cnt--;
else
cnt++;
ans+=bar[cnt+zero];
if (cnt==0)
ans++;
}
printf("%lld",ans);
return 0;
}