Description

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

Solution

经典中位数计数问题，记得以前百度之星也出过类似的题，这道题有一个限定范围是要奇数区间的
我们很容易想到，奇数下标到偶数下标或者偶数下标到奇数下标的长度一定是奇数的
对于每个数字，只可能大于，等于，小于b，于是可以重新分别赋值为1，0，-1
那么维护两个前缀和和一个now，如果当前在奇数下标，查询偶数的前缀和的cnt2[now]，否则查询奇数的前缀和cnt1[now]
now 是 1到i 的前缀和，因为如果有两个位置比如 2 和 5 的前缀和相等，那么必有 3到4 这段区间的和为 0
所以可以通过查表来计算贡献。另外要注意奇数区间下，一定要有一个b，所以还要找下b的位置

Code

#include<iostream>
#include<vector>

using namespace std;

const int N = 1e5 + 5;

int a[N];
int cnt1[N * 3], cnt2[N * 3];
int main() {
    int n, m;
    cin >> n >> m;
    int pos = -1;
    cnt2[N] = 1; 
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] > m) {
            a[i] = 1;
        } else if (a[i] == m) {
            a[i] = 0;
            pos = i;
        } else {
            a[i] = -1;
        }
    }
    int now = 0;
    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        now += a[i];
        if(i & 1) {
            if(i >= pos) {
                ans += cnt2[N + now];
            } else cnt1[N + now]++;
        } else {
            if(i >= pos) {
                ans += cnt1[N + now];
            } else cnt2[N + now]++;
        }
    }
    cout << ans << "\n";
    return 0;
}