题意:
给出 的一个排列,统计该排列有多少个长度为奇数的连续子序列的中位数是
。
题解:
先考虑一段区间中位数为 有什么性质:这一段区间内大于
的数和小于
的数一样多,并且包含
。
然后做一个简单的转化,大于 的数记为
,小于
的数即为
。
那么中位数为 的区间就有:
- 区间包含
所在的位置
,即区间
满足
。
- 转化后的区间和为 0。
求区间和为 的数量有一个常用的技巧:前缀和。
区间 和为
,等价于区间
的和与区间
的和相等,即前缀和
。
然后用一个 map<int, int> 保存前缀和为某个值对应的数量。这样从左至右遍历统计就可以了。
这道题还有和包含位置 的限制条件,这样可以将位置
左边的前缀和对应值存入 map,右边的前缀和则用于查找有多少对应的区间左端点,统计答案。
Code
#include <bits/stdc++.h> using namespace std; int n, b; map<int, int> mmp; int main() { cin >> n >> b; bool left = true; long long sum = 0, ans = 0; mmp[sum]++; for(int i = 1; i <= n; i++) { int x; cin >> x; if(x == b) left = false; else sum += x > b ? 1 : -1; if(left) mmp[sum]++; else ans += mmp[sum]; } cout << ans << endl; return 0; }