题目

• 原题地址：中位数图
• 题目编号：NC19913
• 题目类型：差分、前缀和
• 时间限制：C/C++ 1秒，其他语言2秒
• 空间限制：C/C++ 262144K，其他语言524288K

1.题目大意

• 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。

2.题目分析

• 比b大的设为1，比b小的设为-1；
• 找到b的位置，分别向左向右计算sum；
• 先算左面每个sum的个数，把sum为0的先加上（b本身一个元素也符合题意）
• 在计算右面的sum时把可以与左面匹配（sum值互补）的个数加到答案里。

3.题目代码

#include 

using namespace std;

int a[100005];
int c[200005];
int f[100005];
int ans;

int main() {
    int n, b;
    cin >> n >> b;
    int pos, sum = 0;
    int ans = 0;
    for(int i=0;i> a[i];
        if(a[i]==b)
            pos = i;
        else
            f[i] = a[i]=0;i--)
    {
        sum += f[i];
        c[n-sum]++;
    }
    c[n]++;
    ans += c[n];
    sum = 0;
    for(int i=pos+1;i