每日一题 5.22 [CQOI2009]中位数图

对于这题 我是这样写的
进行预处理 对大于预定的中位数的数设为1 小于设为0
题目意思是要我们找到序列长度为奇数且中位数为预定中位数的序列数
于是我们就转化为 以预定中位数的位置为准 它后面的前缀和+它前面的后缀和等于0即所求序列
于是我们先求出它前面的后缀和并装入桶中 在求它后面的前缀和算贡献
要注意 当单一缀和为0时 可以直接与该中位数组合成一个合格序列

#include <bits/stdc++.h>
#define ll long long
int const N=1e5+5;
using namespace std;
int n,k,a[N],m[N<<1];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    int z,ans=1;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        if(a[i]>k) a[i]=1;
        else if(a[i]<k) a[i]=-1;
        else a[i]=0,z=i;
    }
    int ant=0;
    for(int i=z-1;i>0;--i)
    {
        ant+=a[i];
        m[ant+n]++;
        if(ant==0) ans++;
    }
    ant=0;
    for(int i=z+1;i<=n;++i)
    {
        ant+=a[i];
        ans+=m[n-ant];
        if(ant==0) ans++;
    }
    cout<<ans<<endl;
    return 0;
}