链接:

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述:

第一行为两个正整数n和b ,第二行为1~n 的排列

输出描述:

输出一个整数,即中位数为b的连续子序列个数。

示例1
输入

7 4
5 7 2 4 3 1 6

输出

4

题解:

b是中位数,在b后面的比b大,前面的比b小,比b大多少小多少都无所谓,所以我们可以把大于b的数记为1,小于的记为-1,相等的记为0,这样的话,我们要找一个什么样的区间?一个奇数区间的和是0且0的长度还是奇数(和为0说明左右两边-1和1数量相等,且最中间为0是我们所要的b)
我们可以以0开始分别分析左右两边,统计0的左边后缀和为i的个数,右边的前缀和为i的个数,为了保证两边数量相同,就要使右边的前缀和与左边的前缀和互为相反数。(左右前缀和均从0开始)
样例:
5 7 2 4 3 1 6
化为-1,0,1
1 1 -1 0 -1 -1 1
0的左边前缀和(从0开始)
1 0 -1
右边
-1 -2 -1

左边一个-1可以和右边两个-1搭配,两个答案
左边一个0,不与右边搭配,一个答案
b本身,一个答案
总:四个答案

代码:

(代码仅提供思路)

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 1e6+4
using namespace std;
int a[maxn];
map<int,int >b;
int main()
{
    int n,m;
    cin>>n>>m;
    int pos,sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]<m)a[i]=-1;
        else if(a[i]>m)a[i]=1;
        else 
        {
            a[i]=0;
            pos=i;
        }
    }
    b[0]=1;//和为0则符合条件 
    int tot=0;
    for(int i=pos-1;i;i--)
    {
        if(a[i]==1)sum--;//前缀和 
        else sum++;
        if(sum==0)tot++;//存在0就直接加 
        b[tot]++;
    }
    for(int i=pos+1;i<=n;i++)
    {
        if(a[i]==1)sum--;
        else sum++:
            ans+=b[-sum];//查看相反数有多少个 
    }
    printf("%d",tot);
    return 0;
}