题解 | #[CQOI2009]中位数图#

1. 本题不需要在意数的值，仅仅需要判断输入的数字与中位数b的大小，大存为1，小存为-1，等于存为0
2. 然后判断某一段子序列的和是否为0，且0本身是否存在于此子序列中
3. 可以先从b所在位置向左遍历，求出其前缀和中1，-1，0的个数分别为多少
4. 再从b所在位置向右遍历，每求出一个后缀和就与左边匹配，1与-1匹配，0和0匹配。如：右边后缀和为1，则匹配左边-1的个数，让子序列个数＋左边-1的个数
5. 注意：b本身也可看做一个子序列

#include <iostream>
using namespace std;
#include <stdio.h>

int n, b;
const int arr_size = 100000;
int num[arr_size+5]; //存放输入的数据，以0，1，-1的形式
int temp[arr_size+5]; //存放0， 1， -1的个数

int main(void)
{
    scanf("%d%d", &n, &b);
    int nVal; //存放输入的数据
    int pos; //记录中位数的位置
    int count = 1; //记录连续子序列个数，b本身也是一个子序列
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &nVal);
        if(nVal > b) 
            num[i] = 1;
        else if(nVal < b) 
            num[i] = -1;
        else
            pos = i;
    }
    
    //从中位数的位置向左遍历，求前缀和
    int sum = 0;
    for(int i = pos-1; i >= 1; i--)
    {
        sum += num[i];
        temp[n+sum]++; //size+1记录1的个数，size-1记录-1个数，size记录0个数
        if(0 == sum) count++;
    }
    
    //从中位数向右遍历，求后缀和，并让其与左边的匹配，类似于1与-1对应
    sum = 0;
    for(int i = pos+1; i <= n; i++)
    {
        sum += num[i];
        count += temp[n-sum];
        if(0 == sum) count++;
    }
    printf("%d\n", count);
    return 0;
}