题意

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

后言

看了别人的写法才知道我的写法有多s,b。大家就当看个乐吧TAT

后后言

我靠！原来题目中的数组是 的排列！！！！以下做法适用于任何数组！！！ 可以不止有一个！

分析

直接求中位数是 的区间有多少不好求，我们考虑求中位数大于等于 的区间数 - 中位数大于等于 的区间数，类似一个差分的思想。（当然也可以用中位数小于等于 的区间数 - 中位数小于等于 的区间数）
这样子，我们就把问题转化成一个比较套路的题了，即是求中位数大于等于 的奇数长区间有多少个。
我们令：

  1. 时，
  2. 时，

记 为 的前缀和，即 。
那么区间 满足中位数大于 的条件是什么捏？
其实就是 的区间和大于 ，也就是 。（可以自己写几个数感受一下）
这样，对于一个右端点 ，我们要看满足条件的区间 有多少个，即是看有多少个 ，满足 。这个是可以用树状数组快速查询滴。
不过，由于题目中要求区间长度为奇数，于是我们要对 和 分别维护一个树状数组，当 为奇数时，在偶数的树状数组中查询，反之同理。
还有就是， 可能小于 ，于是我们要给 同时加上一个大数再插入树状数组。
这道题就这样艹完了，复杂度是 的。
具体细节见代码~

代码如下

#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
int a[N], s[N], c1[N * 3], c2[N * 3], n, maxn = 300000;
void add(int *c, int x){
    for(int i = x; i <= maxn; i += i & -i) c[i]++;
}
LL query(int *c, int x){
    LL s = 0;
    for(int i = x; i > 0; i -= i & -i) s += c[i];
    return s;
}
LL cal(int x){
    int i;
    LL tot = 0;
    memset(c1, 0, sizeof(c1));
    memset(c2, 0, sizeof(c2));
    for(i = 1; i <= n; i++){
        if(a[i] >= x) s[i] = s[i - 1] + 1;
        else s[i] = s[i - 1] - 1;
    }//求出 s[i] 
    add(c1, N);//在偶数的树状数组中插入 s[0] + N 
    for(i = 1; i <= n; i++){
        if(i % 2) tot += query(c1, s[i] + N - 1);//如果是奇数，在偶数的树状数组中查询 
        else tot += query(c2, s[i] + N - 1);//反之同理 
        if(i % 2) add(c2, s[i] + N);//如果是奇数，***奇数的树状数组中 
        else add(c1, s[i] + N);//反之同理 
    }
    return tot;//得到中位数大于等于 x 的区间数 
}
int main(){
    int i, j, b;
    n = read(); b = read();
    for(i = 1; i <= n; i++) a[i] = read();
    printf("%lld", cal(b) - cal(b + 1));//差分 
    return 0;
}