[CQOI2009]中位数图

题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

思路：如果我们把比大于k的值变成1，比k小的值变成-1，那么计算从左边到k区间的值，并记录个数，加上为0的个数，再计算从右边到k区间的值，加上相反数的标记个数，如果值为0，再加1，可用map标记；

代码：

#include<bits/stdc++.h>
#define ll long long
#define inf 1000000007

using namespace std;

int a[100005];
map<int,int> ma;

int main()
{
    int n, k;
    int index=-1;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==k)
        {
            index=i;
        }
        else if(a[i]>k)
        {
            a[i]=1;
        }
        else if(a[i]<k)
        {
            a[i]=-1;
        }
    }
    ll z=1;
    int l=index-1,r=index+1,ji=0;
    while(l)
    {
        ji=ji+a[l];
        ma[ji]++;
        l--;
    }
    z=z+ma[0];
    ji=0;
    while(r<=n)
    {
        ji=ji+a[r];
        if(ji==0)
        {
            z++;
        }
        z=z+ma[-ji];
        r++;
    }
    cout << z << endl;
    return 0;
}