题目描述

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

题解：

  • 题目没有给数据范围。。。实测1e5+10能过。
  • 由于是 1~n 的一个排列，所以不用担心数字重复的问题。而且，由于是连续子序列，所以满足答案的序列必须是包含数字 b 的左右区间。
  • 由于是求中位数，所以除了 b 以外的数的具体大小并不重要，重要的是该数比 b 大还是比 b 小。我们用 a[i] = -1 代表该数比 b 小，用 a[i] =1 代表该数比 b 大。
  • 连续区间，很容易让人联想到前缀和。在这题中，我们使用前缀和来表示从当前数到 b 的区间中，比 b 大的数和比 b 小的数的状态（数量）。只需要对 a 数组求前缀和，就可以求出以上数量。
  • 如 s[i] = 2, 就代表区间 [i,b的位置-1] (i<b)中比 b 大的数相较于比 b 小的数多两个。
  • 那我们怎么计算结果呢？如果光看左半区间和右半区间，只有当 s[i] == 0 的时候，才能成立，如果左右两个区间合起来看的话，只需要左右两个区间互为相反，即比 b 大和小的数量加起来相等，就成立。

代码：

#include<iostream>

using namespace std;
const int N = 100010;
const int add = 50005;//因为有负数，为了避免负数访问数组，我们加上一个大数！
long long a[N],s[N];
long long cnt[N];
int main(){
    int n,b;
    cin>>n>>b;
    int pos;
    cnt[add]=1;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        if(a[i]>b) a[i]=1;
        else if(a[i]==b) pos=i;
        else a[i]=-1;
    }

    long long res=1;
    for(int i=pos+1;i<n;i++){
        s[i]=a[i]+s[i-1];
        cnt[s[i]+add]++;
        if(s[i]==0) res++;
    }

    for(int i=pos-1;i>=0;i--){
        s[i]=a[i]+s[i+1];
        res+=cnt[-s[i]+add];
        //cout<<res<<endl;
    }
    //for(int i=0;i<n;i++) cout<<s[i]<<endl;
    cout<<res;
    return 0;
}