不错的思维题
传送门：$>here<$
题意：给出一个N的排列，求出其中有多少个连续子段的中位数是b
数据范围：$N \leq 100000$
$Solution$
先考虑中位数的意义：一个序列中，大于它的与小于它的一样多。而由于中位数已经确定，所以最终的序列一定包含它所在的那个位置。
设$$c[i]=\begin{cases}0 & \text{} a[i]==b \\ 1 & \text{} a[i]>b \\ -1 & \text{} a[i]<b \end{cases}$$
于是如果我们统计一个$sum[i]$表示$c[i]$的前缀和，在开一个桶表示左侧右侧对应的个数。就可以得到答案
$$ans = \sum\limits_{i=-N}^{+N}bl[i]*br[-i]$$
注意下标不能为负数
反思
对于无论是平均数还是中位数，对于计算机来说都不好处理。此时最好的办法就是还原为最简单的求和问题
$my \ code$
/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = ;
const int INF = ;
const int ad = 1e5;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = ; int w = ; register char c = getchar();
for(; c ^ '-' && (c < '' || c > ''); c = getchar());
if(c == '-') w = -, c = getchar();
for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - ''; return x * w;
}
int N,B,pos,Ans;
int a[MAXN],c[MAXN],sum[MAXN],bl[MAXN*],br[MAXN*];
int main(){
N = read(), B = read();
for(int i = ; i <= N; ++i){
a[i] = read();
if(a[i] < B) c[i] = -;
if(a[i] > B) c[i] = ;
if(a[i] == B) pos = i;
sum[i] = sum[i-] + c[i];
}
for(int i = ; i < pos; ++i){
bl[sum[pos-]-sum[i]+ad]++;
}
for(int i = pos; i <= N; ++i){
br[sum[i]-sum[pos]+ad]++;
}
for(int i = -N; i <= N; ++i){
Ans += bl[i+ad] * br[-i+ad];
}
printf("%d", Ans);
return ;
}