[CQOI2009]中位数图（前后缀和（转换思想））

链接：https://ac.nowcoder.com/acm/problem/19913链接：https://ac.nowcoder.com/acm/problem/19913

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

#include<iostream>
using namespace std;
int n,b;
int a[100010];
int sum[100010];
int main()
{
    int pos;
    cin>>n>>b;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]>b)
            a[i]=1;
        else if(a[i]<b)
            a[i]=-1;
        else if(a[i]==b)
        {
            a[i]=0;
            pos=i;
        }
        sum[i]=sum[i-1]+a[i];
    }
    int cnt=0;
    for(int i=pos;i<n;i++)
        for(int j=pos;j>=0;j--)
        {
            if(sum[i]-sum[pos]==sum[j-1]-sum[pos])//后缀和  前缀和
                cnt++;
        }
    cout<<cnt<<endl;//包括自己本生（一个数也有中位数）
    return 0;
}

先将这一串数转换一下：比中位数大的记为1，比中位数小的记为-1，中位数本身记为0

若满足条件，转换后的这一串数相加肯定0（满足这一条件肯定为奇数个数，不用再写程序筛选奇数个数）

从0处往前求后缀和，往后求前缀和，当前后缀和互为相反数的时候，满足题意。