题目

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

输入描述：
第一行为两个正整数n和b ，第二行为1~n 的排列。
对于 30% 的数据中，满足 n≤100；
对于 60% 的数据中，满足 n≤1000；
对于 1100% 的数据中，满足n≤100000,1≤b≤n。

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

解析

这道题我一开始还以为是啥尺取题，没想到就是一道思维题。。。而且我还没看到这是一个1~n的排列orz

首先我们来看看题目：
  1. 既然说要中位数的话，而且题目说了一定是一个奇数长子串，我们就知道：中位数这个数一定在这个子串里面。
  2. 然后子串一定是：大于中位数的数等于小于中位数的数。

算法操作：
  1. 我一开始还想拿两个变量来存，看了大佬的题解之后发现还能这样简单操作：将数组中大于中位数的数设置为1，小于的设置为-1。
  2. 栗子：3为中位数，{5，2，3，8，4，6，7，1}->{1，-1，3，1，1，1，1，-1}。
  3. 这样呢，从中间向两边看，先看左边和右边，用sum统计和值，sum==0的时候就说明1和-1数量一样多了。
  4. 左右都有的情况怎么看呢？你就要加一个数组（num数组），
    统计左边的时候，每种sum的情况（也就是对数的删减情况，下面举例），右边情况求互补的就行了。
  5. 栗子：就拿上面这个：{1，-1，3，1，1，1，1，-1}，我们先从3往左边看，碰到第一个是-1，sum为-1，就让num[n - 1]++。
    碰到第二个是1，求和之后sum是0，就让num[n + 0]++（总体也就是num[n - sum]）。
    然后统计右边的时候，如果碰到sum = 1时，就可以加上num[n - 1]的值了对吧（总体也就是ans += num[n + sum]）。

打代码咯：
  1. 先初始化数组，按上面说的换成1，-1，中位数这样的。
  2. 然后观测左边。
  3. 然后观测右边，顺带就可以统计两边的情况。
  4. 看我代码咯~

AC代码 

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e5 + 7;
int n, b, a[MAX], num[MAX << 1];
//全局变量区

int main() {
    cin >> n >> b;
    int pos = 0;//标记中位数位置
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] > b) a[i] = 1;
        else if (a[i] < b) a[i] = -1;
        else pos = i;
    }
    int sum = 0, ans = 1;
    for (int i = pos - 1; i >= 1; i--) {
        sum += a[i];
        num[n + sum]++;
        if (!sum) ans++;//中位数+左边
    }
    sum = 0;
    for (int i = pos + 1; i <= n; i++) {
        sum += a[i];
        ans += num[n - sum];//左边与右边搭配的情况
        if (!sum) ans++;//中位数+右边
    }
    cout << ans << endl;
    return 0;
}