【每日一题】5月22日 中位数图

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

分析：将奇数序列排序，对于比中位数小的元素 和 比中位数大的元素 的个数是相同的，那么我们将比中位数小的元素 置为-1，比中位数大的元素置为1， 那么合法的序列就是序列元素和为0.

• 我们找到的合法的连续子序列一定是包含中位数b的，。假设中位数b的位置为 .左区间边界一定选择的是 中的位置。右区间边界一定选择的是 中的位置。
• 计算所有合法的区间， 那么我们只先标记中位数b到右区间可能位置的元素和，遍历 位置前缀和标记一遍.
• 然后再遍历左区间边界的所有可能，依次作后缀和，查询右边界的前缀和是否有当前后缀和的相反数.答案进行更新即可。
• 可以证明左边区间的值与右边区间的值(x,y)，如果x=-y, 那么序列的元素一定是奇数，因为左边加右边区间元素是 .2*z表示的是区间某一段可能为(-1,1)之类的情况.这个表达式一定为偶数，然后加上中位数b，那么序列元素一定为奇数个.

#include<bits/stdc++.h>
using namespace std;

int mp[200005],a[100005];

int main()
{
    int n,b,pos;
    cin>>n>>b;
    for( int i=1;i<=n;i++ ) 
    {
        cin>>a[i];
        if( a[i]<b ) a[i]=-1;
        if( a[i]>b ) a[i]=1;
        if( a[i]==b ) pos=i;
    }
    int ans=1,sum=0;
    for( int i=pos+1;i<=n;i++ )
    {
        sum+=a[i];
        if( sum==0 ) ans++;
        mp[n+sum]++;
    }
    sum=0;
    for( int j=pos-1;j>=1;j-- )
    {
        sum+=a[j];
        if( sum==0 ) ans++;
        ans+=mp[n-sum];
    }
    cout<<ans<<endl;
}