中位数（median.cpp）
【题目描述】有一个长度为N的数列{A1,A2,...An}，这N和数字恰好是1..N的一个排列。你需要统计有多少个子序列{Ai,Ai+1,...Aj}满足：i<=j且j-i+1为奇数，序列的中位数为B。例如{5,1,3}的中位数为3。
【输入文件】
第一行包含两个正整数N和B；第二行包含N个整数，第i个整数为Ai。
【输出文件】
仅包含一个整数，为满足条件的子序列的个数。
【样例输入】
7 4
5 7 2 4 3 1 6
【样例输出】
4
【数据规模】
对于30%的数据中，满足N<=100；
对于60%的数据中，满足N<=1000；
对于100%的数据中，满足N<=100000,1<=B<=N。
——————————————————————————————————
【题解】【规律+递推】
【因为B是序列的中位数，所以B一定存在于序列中，所以，记录B在序列中的位置num，并把相对应的数置为0；把小于B的数置为-1；大于B的数置为1。】
【分别从num向左向右扫描，并分别设一个累加器，将枚举时遇到的0、1、-1都加入累加器里，并分别用L、R数组记录累加器中每个数出现的次数】
【最后求：∑L[i]*R[-i]（但因为C++没有负数下标，所以要整体向右移n个下标）】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100010],L[200010],R[200010],n,b,num,ans;
int main()
{
freopen("median.in","r",stdin);
freopen("median.out","w",stdout);
int i,j;
scanf("%d%d",&n,&b);
for(i=1;i<=n;++i)
{
scanf("%d",&a[i]);
if(a[i]==b) {num=i; a[i]=0; continue;}
if(a[i]>b) a[i]=1;
else a[i]=-1;
}
int l=n,r=n;
for(i=num;i>0;--i) l+=a[i],L[l]++;
for(i=num;i<=n;++i) r+=a[i],R[r]++;
int len=2*n;
for(i=0;i<=len;++i)
ans+=(L[i]*R[len-i]);
printf("%d\n",ans);
return 0;
}