【每日一题】【5月22日】[CQOI2009]中位数图

题意：

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

题解：

先考虑一段区间中位数为 有什么性质：这一段区间内大于 的数和小于 的数一样多，并且包含 。
然后做一个简单的转化，大于 的数记为 ，小于 的数即为 。
那么中位数为 的区间就有：

• 区间包含 所在的位置 ，即区间 满足 。
• 转化后的区间和为 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;
}