[CQOI2009]中位数图（思维+前缀和）

题目：

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。
对于 1100% 的数据中，满足n≤100000,1≤b≤n。

做法：

第一时间想着stl暴力搞搞，但写着写着发现没必要写这么麻烦。后来补了个简单写法。（但是时间居然差不多）
b作为中位数，我们不关心其他的数的具体值。所以序列中的数我们这样处理：大于b的设为1，小于b的设为-1，b则设为0，然后做一个前缀和数组prefix[]。由于是排列所以只会出现一个b，设它的位置为pos。将序列的奇数位和偶数位分开考虑。从pos往后扫。当前位置是奇数位，则在前面的偶数位中找有多少个prefix[j] == prefix[i]，累加进ans即可，。偶数位同理。不理解的看下面样例：

pos是4，所以i从4扫到7
i = 4 时： j = 1，3满足条件。（这里满足条件指的是区间[j+1,i]就是我们需要的一个中位数区间）
i = 5 时： j = 0满足条件。
i = 7 时： j = 0满足条件。
所以ans = 4。

代码：

简单写法：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, a[N], k, prefix[N], pos;
map<int,int> even, odd;
int main(void){ 
    IOS;
    cin >> n >> k;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        if (a[i] < k) a[i] = -1;
        else if (a[i] > k) a[i] = 1;
        else a[i] = 0, pos = i;
        prefix[i] = prefix[i-1]+a[i];

    }
    for (int i = 0; i < pos; ++i){
        if (i%2) odd[prefix[i]]++;
        else even[prefix[i]]++;
    }
    int ans = 0;
    for (int i = pos; i <= n; ++i){
        if (i%2) ans += even[prefix[i]];
        else ans += odd[prefix[i]];
    }
    cout << ans << endl;
    return 0;
}

stl暴力代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int n, a[N], k, prefix[N], pos;
unordered_map<int, vector<int> > odd, even;
int main(void){ 
    IOS;
    cin >> n >> k;
    even[0].push_back(0);
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        if (a[i] < k) a[i] = -1;
        else if (a[i] > k) a[i] = 1;
        else a[i] = 0, pos = i;
        prefix[i] = prefix[i-1]+a[i];
        if (pos != i){
            if (i%2 == 0) even[prefix[i]].push_back(i);
            else odd[prefix[i]].push_back(i);
        }
    }
    int ans = 0;
    if (pos > 1){
        int x = prefix[pos-1];
        if (pos%2){
            vector<int>& v = even[x];
            int num = upper_bound(v.begin(), v.end(), pos-1) - v.begin();
            if (num) ans += num-1;
        }else{
            vector<int>& v = odd[x];
            int num = upper_bound(v.begin(), v.end(), pos-1) - v.begin();
            if (num) ans += num-1;
        }
    }
    for (int i = pos+1; i <= n; ++i){
        int x = prefix[i];
        if (i%2){
            vector<int>& v = even[x];
            int num = upper_bound(v.begin(), v.end(), pos) - v.begin();
            ans += num;
        }else{
            vector<int>& v = odd[x];
            int num = upper_bound(v.begin(), v.end(), pos) - v.begin();
            ans += num;
        }
    }
    cout << ans+1 << endl; 
    return 0;
}