【每日一题】中位数图

解题思路

符合题意的序列：包含 b 的连续子序列，且序列中大于 b 的值的数目与小于 b 的值的数目相等。

使用 map 记录 b 值所在位置 pos 左边的每个连续子序列中，大于 b 值的数目与小于 b 值的数目之差 tmp 的个数，小于 b 减 1，大于 b 加 1。
当两者数目相等时，tmp = 0，序列符合。
遍历 pos 右边子序列，将与当前差值相反的数目累加计入结果。

C++代码

#include<iostream>
#include<map>
using namespace std;

int main(){
    int n, b;
    cin >> n >> b;
    int arr[n];
    int pos = 0;
    for(int i=0; i<n; ++i){
        cin >> arr[i];
        if(arr[i] == b)
            pos = i;    // 记录b的位置
    }

    int ans = 1;    // b本身就符合题意
    map<int, int> mp;
    int tmp = 0;
    for(int i=pos-1; i>=0; --i){
        if(arr[i] < b)
            --tmp;
        else
            ++tmp;

        mp[tmp] += 1;
        if(tmp == 0)
            ++ans;
    }

    tmp = 0;
    for(int i=pos+1; i<n; ++i){
        if(arr[i] < b)
            --tmp;
        else
            ++tmp;

        if(tmp == 0)
            ++ans;
        ans += mp[-tmp];
    }

    cout << ans << endl;
    return 0;
}