链接：https://ac.nowcoder.com/acm/problem/19913
来源：牛客网
题号：NC19913
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

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

输入描述: 

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

输出描述: 

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

输入

复制 7 4 5 7 2 4 3 1 6 
7 4
5 7 2 4 3 1 6

输出

复制 4 
4

本题是一个前缀和和差分的变题，可以让小于b的数设置为-1，大于b的数的值设置为1。然后通过查看相加后的结果是否是0来判断是否是中位数（也就相当于b这个数左右两边的数数量一致，那么b一定是一个中位数）。然后就是如何记录的问题？可以先想左遍历如果相加的值等于0那么让结果ans加一，同时搞一个数组记录左边各种和的数量。然后在遍历右边的时候一边相加的值是否是0，一边看与右边各种和是否有对应的，如果有也可以直接加上。

代码： 
//1 2 3 4 5 6 7
//使用差分求和的方式
#include <iostream>
#include <cstdio>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;


int main() {
    IOS;
    int n, b, num;
    cin>>n>>b;
    int pos;
    int a[n+1];
    for (int i=1;i<=n;i++) {
        cin>>num;
        if (num<b) {
            a[i] = -1;
        }
        if (num>b) {
            a[i] = 1;
        }
        if (num==b) {
            pos = i;
            a[i] = 0;
        }
    }
    const int maxn = 1e5+7;
    int nm[maxn] = {};
    //ans从1起步，因为还有自身这一个因素，所以至少是1
    int sum = 0, ans = 1;
    for (int i=pos-1;i>0;i--) {
        sum += a[i];
        nm[n+sum]++;
        if (sum==0) {
            ans++;
        }
    }
    sum = 0;
    for (int i=pos+1;i<=n;i++) {
        sum += a[i];
        ans += nm[n-sum];
        if (sum==0) {
            ans++;
        }
    }
    cout<<ans;
    
    
    
    return 0;
}