Mas's Blog
Masellum 的生活日志
[CQOI2009] 中位数

题目

题目链接

题目描述

给出 1n1 \sim n 的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是 bb。中位数是指把所有元素从小到大排列后,位于中间的数。

输入输出格式

输入格式:

第一行为两个正整数 nnbb,第二行为 1n1 \sim n 的排列。

输出格式:

输出一个整数,即中位数为 bb 的连续子序列个数。

数据规模与约定

对于 30%30\% 的数据中,满足 n100n \leq 100

对于 60%60\% 的数据中,满足 n1000n \leq 1000

对于 100%100\% 的数据中,满足 n100000,1bnn \leq 100000, 1 \leq b \leq n

题解

在这个问题中,由于中位数已给定为 bb,所以我们可以不再关心元素们的具体值,而只关心它们与 bb 的相对大小关系。容易想到,如果把所有小于 bb 的数替换为 1-1,所有大于 bb 的数替换为 11,那么一个和为 00 的连续区间中大于 bb 的数的数量与小于 bb 的数的数量相同。如果 bb 在这个区间内,那么这个区间就是一个符合要求的区间。我们考虑怎样去求这样的区间的个数。

进一步考虑,既然这样的区间必须包括 bb,那么我们不妨从 bb 所在的位置开始向左右两边分别统计区间和,如果从 bb 开始向左的某个区间的区间和等于从 bb 开始向右某个区间的区间和的相反数,那么这两个区间可以拼成一整个和为 00(也就是中位数为 bb 的区间)。所以先从 bb 向左统计,开一个桶统计某个区间和的值出现的个数(可以使用数组,但要处理负数,于是我用了 std::map 代替);之后再次向右统计,考虑对于每个区间和的值,从 bb 向左的每个区间和等于这个值的相反数的区间都可以和我们目前统计到的向右的区间拼成一个中位数为 bb 的区间,用乘法原理的思想统计答案即可。注意对于 bb 为区间端点的情况要小小地特判一下。

代码

Finita la comedia.