solution

处理出一个数组t,如果那么,否则

然后我们只要找到一个包含b所在位置的区间满足就可说明这个区间内的中位数为

所以对求一遍前缀和,记录下所在位置左边的所有前缀和值的数量。然后枚举所在位置的右边,统计答案即可。

code

/*
* @Author: wxyww
* @Date:   2020-05-21 19:50:52
* @Last Modified time: 2020-05-21 19:56:26
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
ll ans;

int ma[N + N],sum,a[N],K;
int main() {
    int n = read(),b = read();
    ma[n] = 1;
    for(int i = 1;i <= n;++i) {
        a[i] = read();
        if(a[i] == b) K = i;
        if(a[i] >= b) sum++;
        else sum--;
        if(!K) ma[sum + n]++;
        else {
            ans += ma[sum - 1 + n];
        }
    }

    cout<<ans<<endl;
    return 0;
}