[CQOI2009]中位数图 题解

考点:预处理 思维 前缀和后缀和
首先输入的数字是什么我们没必要去记录他，比k大的就赋值为1，比k小就赋值为-1，相等就为0.
首先我们应该可以很好的想到如果有一段连续的奇数序列的和为0的话，并且中间要有0这个数，那么这一段序列就是符合条件的。
重点是我们如何去判断有多少个连续的奇数序列和为0.
我们可以考虑前缀和和后缀和，然后用数组储存对应值的个数，注意下标要做一些处理，否则负数会越界，这里可以+n。
然后把对应的位置进行求值，就比如-5的位置和5的位置进行乘积，就是对应的个数，这里可以使用双指针进行处理。
最后需要单独加值为0（下标为n）的位置的个数，因为它可以自己成一个序列，ans求和即可。

import java.util.*;
import java.math.*;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.PrintWriter;
public class Main {
    public static void main(String args[])throws IOException
    {
         StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int m = (int)in.nval;
        int num[] = new int[n];
        int q=0;
        for(int t=0;t<n;t++)
        {
            in.nextToken();
            int x = (int)in.nval;
            if(x==m)
            {
                num[t] = 0;
                q=t;
            }
            else if(x>m)
                num[t] = 1;
            else if(x<m)
                num[t] = -1;
        }
        int nextq[] = new int[2*n];
        int nexth[] = new int[2*n];
        int sum=0;
        for(int i=q-1;i>=0;i--)
        {
            sum+=num[i];
            nextq[sum+n]++;
        }
        sum=0;
        for(int i=q+1;i<n;i++)
        {
            sum+=num[i];
            nexth[sum+n]++;
        }
        int ans = 1;
        for(int i=1,j=2*n-1;j>=1&&i<2*n;i++,j--)
        {
                ans+=(nextq[i]*nexth[j]);
        }
        ans+=nextq[n];
        ans+=nexth[n];
        out.println(ans);
        out.flush();

   }
 }