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

先看题：

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

说明b本身是中位数而且b是包含在连续子序列中的，
那么我们就可以简化一下输入将1~n的数变成{-1，1，0}（小于b：-1，大于b：1，等于b：0）
那么求中位数为b的序列个数就变成了求：左边的序列和+右边序列和==0的序列个数

AC代码Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int b = in.nextInt();
        int[] a = new int[n];
        int[] c = new int[n << 1];
        int idx = -1;
        for (int i = 0; i < n; ++i) {
            int k = in.nextInt();
            a[i] = k > b ? 1 : -1;
            if (k == b) {
                a[i] = 0;
                idx = i;
            }
        }
        int cnt = 1;//中位数本身
        int sum = 0;
        for (int i = idx - 1; i >= 0; --i) {
            sum += a[i];//后缀和
            ++c[n + sum];//记录后缀和的个数n+是向后移动n位避免下标为负数
            if (sum == 0)// 说明下标为i的数到b的中位数为b
                ++cnt;
        }
        sum = 0;
        for (int i = idx + 1; i < n; ++i) {
            sum += a[i];// 前缀和
            cnt += c[n - sum];// 与中位数的左半部分和为零的数的个数 
            if (sum == 0)
                ++cnt;
        }
        System.out.println(cnt);
    }
}