题目

Description

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

Input

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output

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

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

4
Hint
第三个样例解释：{4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}
N<=100000

题解

从一串数字中(无规律)寻找一个子串,使得该子串的中位数为要求的数,求子串的组数

由于数字本身没有规律,而寻找中位数需要规律,因此如果暴力解决需要 O(n3logn)
显然这种时间复杂度很不靠谱

由于数字不存在重复( 1 ~ n ),并且选取的子串的数字个数必然是奇数,因此可以采用一些性质来计算

首先,中位数是一串数中,比它大的数和比它小的数个数相同的数
因此可以先将数据处理成是否比要求的数大的形式(大于记为 1 ,小于记为 2 ,等于记为 0 )
然后再使用 O(n) 的时间处理信息,分别计算从目标的数向左、向右抵消后仍然比该数大的个数
用 map 记录一侧的的数达到某个数的组数,然后在另一侧将能与其抵消的相加起来,最后的数就是答案
( 0 要特殊考虑)

样例解释如下:

将左侧(包括目标数)的数映射成 map 有

则针对右侧的数据,结果为 ans = 2 + map[1] + map[2] + map[1]
其中 2 是 map 里 0 的个数

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

typedef long long LL;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 100005;

int n,k;
int a[maxn];
int dp[maxn];

map<int,int> m;

bool Do() {

    if(!(cin >> n >> k))
        return false;

    int pos;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
        if(a[i] == k)
            pos = i;
    }

    m.clear();
    dp[pos] = 0;
    int ans = 1;
    m.insert(pair<int,int>(0,1));

    for(int i = pos - 1;i >= 0;i--) {
        dp[i] = dp[i + 1] + ((a[i] > k) ? 1 : -1);
        
        if(dp[i] == 0)
            ans++;

        if(m.count(dp[i])==0)
            m.insert(pair<int,int>(dp[i],0));
        m[dp[i]]++;
    }

    for(int i = pos + 1;i < n;i++) {
        dp[i] = dp[i - 1] + ((a[i] > k) ? 1 : -1);

        if(m.count(-dp[i]) == 1)
            ans += m[-dp[i]];
    }

    cout << ans << endl;

    return true;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    while(Do());

    return 0;
}