题目描述

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

题解：

由于题目所给的是一个排列，即1~n每个数值出现一次，那么一个连续的子序列要想包含b只有3中情况，假设b在pos

1. i ~ pos
2. pos ~ j
3. i ~ pos ~ j
   并且由于中位数只可以 为b，那么所有数也可以分为3类，>b <b ==b,我们把 >b 看成1 ,< b 看成-1.
   所以对于情况 1 2 只要从pos开始分别向前向后累加，和为0时即为一种有效情况。
   对于情况 3 也只需要先统计一下，左边所有和能出现的情况，然后在扫描右边的时候假设当前和为 s ，我们只需要找到-s在左边出现了多少次就可以了

由于在统计过程中会出现和 小于 0 的情况，我们可以把所有和全加n，或者用map解决这个问题

代码；

  #include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define fi first
#define se second
#define pb push_back
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const  ll inf  = 0x3f3f3f3f3f3f3f3f;
const int mod  = 998244353;
const int maxn = 2e6 + 4;
const int N    = 5e3 + 5;
const double eps = 1e-6;
const double pi = acos(-1);
ll qpow(ll x,ll y){ll ans=1;x%=mod;while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1;}return ans;}


int n,b,a[maxn],pos,c[maxn],s,ans;
int main(){
    //freopen("a.in","r",stdin);
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==b) pos=i;
        else if(a[i]>b) a[i]=1;
        else if(a[i]<b)  a[i]=-1;

    }
    for(int i=pos-1;i>=1;i--){
        s+=a[i];
        c[s+n]++;
        if(!s) ans++;
    }
    s^=s;
    for(int i=pos+1;i<=n;i++){
        s+=a[i];
        ans+=c[n-s];
        if(!s) ans++;
    }
    printf("%d\n",ans+1);

}
/*


*/