题解 | #[CQOI2009]中位数图#

奇数序列的中位数：大于它的数的个数和小于它的数的个数相等。

根据上述性质对排列进行等价转换：

• 如果某个数字大于 ，则将其转换成

• 如果某个数字小于 ，则将其转换成

• 如果某个数字等于 ，则将其转换成 ，记录下该位置

则题目要求转换成 “求连续一段长度为奇数的序列，满足序列和为 ”。

    int n, b;
    cin >> n >> b;
    vector<int> cmps(n);
    int flag;
    for (int i = 0; i < n; ++i)
    {
        cin >> cmps[i];
        if (cmps[i] == b)
        {
            flag = i;
            cmps[i] = 0;
        }
        else
        if (cmps[i] > b)
        {
            cmps[i] = 1;
        }
        else
        if (cmps[i] < b)
        {
            cmps[i] = -1;
        }
    }

接下来考虑求区间的方案。

• 有且仅有一个与中位数相等的数，一个数算作一个排列， 初始化为

• 由于是奇数序列，一定要包含下标为 的数

• 由前两条：序列分 种情况：

  1. 单独一个数

  2. 从 位置向左直到某个位置

  3. 从 位置向右直到某个位置

  4. 从 左侧某个位置向右直到 右侧某个位置

由于上边对序列做了转换，我们使用 前缀和 的方式记录下所有某个位置到 这段序列的序列和，并记录下各个序列和的值出现的次数。

首先对 的一侧求前缀和（我选择右侧），

当某个位置的前缀和为 时，则 到该位置的序列和为 ，即该序列满足情况 ，++。

另外，我选择将 处的 算到右边，便于下一步将情况 和情况 放在一起考虑。

    int ans = 1;
 
    map<int, int> counts_r;
    ++counts_r[0];
    vector<int> sums_r(n);
    for (int i = flag + 1; i < n; ++i)
    {
        sums_r[i] = sums_r[i - 1] + cmps[i];
        ++counts_r[sums_r[i]];
        if (sums_r[i] == 0)
            ++ans;
    }

然后对 的另一侧求后缀和（左侧），

对于每个位置，求出前缀和之后，查询右侧前缀和中是否存在其相反数，每存在一个，则说明该有一个区间和为 ，++。

    vector<int> sums_l(n);
    for (int i = flag - 1; i >= 0; --i)
    {
        sums_l[i] = sums_l[i + 1] + cmps[i];
        ans += counts_r[-sums_l[i]];
    }

最后输出 即可、 附完整代码如下：

void Solve(void)
{
	int n, b;
	cin >> n >> b;
	vector<int> cmps(n);
	int flag;
	for (int i = 0; i < n; ++i)
	{
		cin >> cmps[i];
		if (cmps[i] == b)
		{
			flag = i;
			cmps[i] = 0;
		}
		else
		if (cmps[i] > b)
		{
			cmps[i] = 1;
		}
		else
		if (cmps[i] < b)
		{
			cmps[i] = -1;
		}
	}

	int ans = 1;

	map<int, int> counts_r;
	++counts_r[0];
	vector<int> sums_r(n);
	for (int i = flag + 1; i < n; ++i)
	{
		sums_r[i] = sums_r[i - 1] + cmps[i];
		++counts_r[sums_r[i]];
		if (sums_r[i] == 0)
			++ans;
	}
	vector<int> sums_l(n);
	for (int i = flag - 1; i >= 0; --i)
	{
		sums_l[i] = sums_l[i + 1] + cmps[i];
		ans += counts_r[-sums_l[i]];
	}
	cout << ans << endl;
}