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; }