分析
中位数是指把所有元素从小到大排列后，位于中间的数。
由于题目要求的是长度为奇数的子序列，又由中位数的定义，我们可以知道，一段满足要求的序列中，比\(b\)大的数一定和比\(b\)小的数一样多，我们只关心每个数与\(b\)的大小关系，而不是它的具体值，所以我们可以将每个数标记为\(1\)和\(-1\)，如果它大于\(b\)，则标为\(1\)，否则标为\(-1\)。
于是我们可以利用差分的思想。记下\(b\)的位置为\(pos\)，将\(pos\)两端分别开始扫，记录前缀和。
如果\(pos\)一端的某段前缀和值为\(3\)，则说明这一段还需要\(3\)个小于\(b\)的数，于是在\(pos\)的另一端找到前缀和为\(-3\)的即可，这两段合起来再加上\(b\)本身即为一段满足要求的序列。
优化：利用桶记录\(pos\)一段的前缀和的值。
代码
#include#include #include #include #define il inline#define re register#define tie0 cin.tie(0),cout.tie(0)#define fastio ios::sync_with_stdio(false)#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)using namespace std;typedef long long ll;template inline void read(T &x) { T f = 1; x = 0; char c; for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1; for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48); x *= f;}int n, b, pos, cnt;int a[100005], pre[100005], last[100005],ton[100005];int main() { read(n), read(b); for (int i = 1; i <= n; ++i) { read(a[i]); if (a[i] < b) a[i] = -1; else if (a[i] > b) a[i] = 1; else if (a[i] == b) pos = i; } for (int i = pos - 1; i; --i) { pre[i] = pre[i + 1] + a[i]; if (!pre[i]) cnt++; ton[-pre[i]]++; } for (int i = pos + 1; i <= n; ++i) { last[i] = last[i - 1] + a[i]; if (!last[i]) cnt++; } /*for (int i = pos - 1; i; --i) 这样写会超时 for (int j = pos + 1; j <= n; ++j) if (pre[i] + last[j] == 0) cnt++;*/ for (int i = pos + 1; i <= n; ++i) cnt += ton[last[i]]; printf("%d", cnt + 1);//加上它本身 return 0;}