题目：NC19913 / 洛谷 P1627

题目回顾

给定一个 $1 \sim n$ 的排列和一个数 $b$，统计有多少个长度为奇数的连续子序列，其中位数恰好为 $b$。

数据范围：$n \le 10^5$。

中位数的定义：在一个长度为奇数的序列中，大于中位数的元素个数 = 小于中位数的元素个数。

正解：前缀和 + 计数

核心思路

中位数的本质是「大于 $b$ 和小于 $b$ 的元素个数相等」。如果我们给每个元素赋一个值来标记它与 $b$ 的大小关系，那么包含 $b$ 的子区间合法，当且仅当左右两边的标记值之和为 0。

这样一来，问题转化为：以 $b$ 为分界，左边统计每种「后缀和」出现了多少次，右边用「前缀和」去匹配相反数，$O(n)$ 即可完成。

逐步推导

Step 1：序列转化

将原序列按与 $b$ 的大小关系替换为 $+1 / -1 / 0$：

for (int i = 1; i <= n; i++) {
    int x; cin >> x;
    if (x > b)      a[i] = 1;
    else if (x == b) { a[i] = 0; pos = i; }
    else            a[i] = -1;
}

转化后，中位数条件变为：区间内所有元素之和为 $0$（因为 $+1$ 和 $-1$ 数量相等）。

Step 2：以 $b$ 为锚点拆分

由于 $b$ 在排列中唯一，设其位置为 $pos$。任意包含 $b$ 的子区间可以拆成三段：

$$ [\underbrace{L,\ \dots,\ pos-1}_{\text{左边部分}},\ \underbrace{pos}_{0},\ \underbrace{pos+1,\ \dots,\ R}_{\text{右边部分}}] $$

• 左边部分的和记为 $sum_L$
• 右边部分的和记为 $sum_R$
• $b$ 本身贡献 $0$

合法条件：$sum_L + sum_R = 0$，即 $sum_R = -sum_L$。

长度奇数的条件自动满足：$b$ 占一位，左右各 $k$ 个 $+1$ 和 $k$ 个 $-1$ 配对，总长 $1 + 2k$ 必为奇数，无需单独判断。

Step 3：向左扫描，统计后缀和频次

从 $pos-1$ 向左遍历，累加后缀和 $sum$，用数组 $cnt$ 记录每种和值出现了多少次。

int offset = n;          // 偏移量，把负数映射到非负下标
cnt[offset] = 1;         // 左边取 0 个元素，和为 0 算一种方案
int sum = 0;
for (int j = pos - 1; j >= 1; j--) {
    sum += a[j];
    cnt[sum + offset]++;
}

cnt[offset] = 1 的含义：$b$ 左边一个都不取也是一种合法的「左边选择」，对应子序列以 $b$ 本身开头。

Step 4：向右扫描，匹配相反数

从 $pos+1$ 向右遍历，累加前缀和 $sum$，每走一步就在 $cnt$ 中查找 $-sum$ 出现了多少次——每个匹配都对应一个合法子区间。

sum = 0;
ans += cnt[offset];      // 右边取 0 个：只取 b 本身
for (int j = pos + 1; j <= n; j++) {
    sum += a[j];
    ans += cnt[-sum + offset];
}

第一行 ans += cnt[offset] 处理的是右边一个都不取的情况（即子区间右端点就是 $pos$）；循环内处理右边至少取一个的情况。

几个关键细节

为什么用偏移量？

后缀和 / 前缀和的范围是 $[-n, n]$，C++ 数组下标不能为负，加偏移量 $n$ 后映射到 $[0, 2n]$。数组大小至少开到 $2n + 5$。

为什么 ans 用 long long？

最坏情况下（如整个序列关于 $b$ 对称），合法子序列数约为 $n^2 / 2$，$n = 10^5$ 时远超 int 上限，必须用 long long。

会不会重复计算？

不会。$pos$ 作为基准点是唯一的：左边统计的是「起点选择」的可能数，右边每走一步就用当前前缀和去匹配左边已有的后缀和，每个子区间对应唯一的 $(L, R)$ 组合，不重不漏。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000;
int cnt[2 * MAXN + 5];

int main() {
    int n, b;
    cin >> n >> b;

    vector<int> a(n + 5);
    int pos = 0;

    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (x > b)
            a[i] = 1;
        else if (x == b) {
            a[i] = 0;
            pos = i;
        } else {
            a[i] = -1;
        }
    }

    int offset = n;
    long long ans = 0;

    // 左边：统计后缀和频次
    cnt[offset] = 1;          // 左边取 0 个
    int sum = 0;
    for (int j = pos - 1; j >= 1; j--) {
        sum += a[j];
        cnt[sum + offset]++;
    }

    // 右边：匹配前缀和
    sum = 0;
    ans += cnt[offset];       // 右边取 0 个（子区间就是 [b] 本身）
    for (int j = pos + 1; j <= n; j++) {
        sum += a[j];
        ans += cnt[-sum + offset];
    }

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

复杂度

关键技巧总结

1. 数值转化：把大小关系映射为 $+1 / -1 / 0$，将「中位数判定」转化为「区间和为 0」
2. 锚点拆分：利用 $b$ 的唯一性，以 $pos$ 为界分别统计左右，避免 $O(n^2)$ 枚举端点
3. 计数数组 + 偏移量：用 $cnt$ 记录后缀和频次，偏移量处理负数下标
4. 左右独立 + 匹配：左边只管统计，右边只管查表，一次扫描出答案