给出一个 \(n\) 的排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 \(k\)

\(n\leq10^5\)

---

有关中位数的 \(trick\) ：因为不需要每个数的值，因此将原序列化为 \(a_i=\begin{cases}-1&(a_i<k)\\0&(a_i=k)\\1&(a_i>k)\end{cases}\)

因此原问题就变成了

给出一个 \(n\) 的排列，统计该排列有多少个包含 \(k\) 的连续子序列的和为 \(0\)

即求 \(\displaystyle\sum_{i=1}^{pos}\sum_{j=pos}^{n}[s_j-s_{i-1}=0]\)

所以我们只需枚举 \(i\) 并计数 \(\displaystyle\sum_{j=pos}^n[s_j=s_{i-1}]\)，暴力存一下即可

时间复杂度 \(O(n)\)

代码

#include 
    
     using namespace std;const int maxn = 1e5 + 10;int n, k, a[maxn], s[maxn], c[maxn << 1];int main() {    scanf("%d %d", &n, &k);    int pos; long long ans = 0;    for (int i = 1, x; i <= n; i++) {        scanf("%d", &x);        if (x > k) a[i] = 1;        if (x < k) a[i] = -1;        if (x == k) a[i] = 0, pos = i;        s[i] = s[i - 1] + a[i];    }    for (int i = pos; i <= n; i++) {        c[s[i] + n]++;    }    for (int i = 1; i <= pos; i++) {        ans += c[n + s[i - 1]];    }    printf("%lld", ans);    return 0;}