题目描述

给出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);

}
/*


*/