题解 | #[CQOI2009]中位数图#

题解：

可以先找到需要的中位数的位置再从这个位置依次向两边寻找答案，因为是中位数所以可以将输入的数据转换成相对的大小比如大于该数就是1，小于就是-1.首先用sum记录当前的集合之和如果等于零代表了当前是一种答案，但这种只能看两边是否有答案，如果在该位置左右呢，那么就需要有一个数组记录左边每一个可能取值的数量，在遍历右边时可以当前的值看左边可能的答案数，比如如果左边某个位置时sum=1,则引入num数组用num[f-sum]记录当右边sum=-1时可能的答案数(f为中位数的位置)比如到右边时可以直接ans+=num[f+sum]，具体代码如下

#include <iostream>
using namespace std;
int a[100010];
int num[200010];
int main()
{
    int n,b;
    cin>>n>>b;
    int ans=1;
    int f=0;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(x>b)
            x=1;
        else if(x<b)
            x=-1;
        if(x==b)
            f=i;
        a[i]=x;
    }
    for(int i=f-1;i>=0;i--)
    {
        sum+=a[i];
        num[f-sum]++;
        if(sum==0)
            ans++;
    }
    sum=0;
    for(int i=f+1;i<n;i++)
    {
        sum+=a[i];
        if(sum==0)
            ans++;
        ans+=num[f+sum];
    }
    cout<<ans;
    return 0;
}