传送门

要求有多少个长度为奇数的区间满足某个数为区间中位数

这样的区间,大于中位数的数个数 等于 小于中位数的数个数

用类似于前缀和的方法,设\(X_i\)为\(i\)和数\(b\)形成的区间内,大于\(b\)的数个数减去小于\(b\)的数个数的值,每次从前面那个位置转移过来,加上这个位置的贡献救星

最后用两个桶统计\(b\)左边和右边的\(X_i\)为某个值的个数,分别记为\(l_i\ r_i\),然后答案为\(\sum_{i,j}l_ir_j\ (i+j==0)\)

注意负下标处理和两个初值要赋

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define LL long long

#define il inline

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define inf 999999999

using namespace std;

const int N=100000+10;

il LL rd()

{

    re LL x=0,w=1;re char ch=0;

    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

    return x*w;

}

int n,b,w,a[N],x[N],l[N<<1],r[N<<1];

LL ans;

int main()

{

  n=rd(),b=rd();

  for(int i=1;i<=n;i++)

    {

      a[i]=rd();

      if(a[i]==b) w=i;

    }

  l[n]=r[n]=1;

  for(int i=w+1;i<=n;i++) x[i]=x[i-1]+(a[i]>b?1:-1),++r[x[i]+n];

  for(int i=w-1;i>=1;i--) x[i]=x[i+1]+(a[i]>b?1:-1),++l[x[i]+n];

  for(int i=0;i<=(n<<1);i++) ans+=1ll*l[i]*r[(n<<1)-i];

  printf("%lld\n",ans);

  return 0;

}