牛客——中位数图（思维）

[CQOI2009]中位数图 （思维）

思路：

感觉这个题很偏向思维，原谅本蒟蒻看了题解后才想明白。

首先要考虑到的就是题目中的大小关系都只是一个相对的关系，所以大于b的数对答案的贡献都是一样的，小于b的数对答案的贡献都是一样的。不妨就设大于b的数的值为1，小于b的数的值为-1，等于b的数的值为0。

所以问题就转化成了求一个区间和为0的而且内部元素有0的长度为奇数的区间个数。

因为1和-1要相互抵消，而区间内又必须含有0，所以区间的长度就一定是奇数。

所以可以以0为起点，分别统计前后缀，前缀和为x时，后缀和一定为-x才能符合题意。所以分别用l,r两个数组表示和为x的数的个数，最后遍历一遍求出结果即可。

因为数组的下标不可以为负数，所以要同时平移，当所有的数都是-1时，和为-n，所以平移n个单位即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=110000;

int a[maxn],l[maxn],r[maxn],sum[maxn];

int main(){
    int n,b;
    cin>>n>>b;
    int pos;
    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 a[i]=0,pos=i;
    }
    l[n]=r[n]=1;
    for(int i=pos+1;i<=n;i++) sum[i]=sum[i-1]+a[i],r[sum[i]+n]++;
    for(int i=pos-1;i>=1;i--) sum[i]=sum[i+1]+a[i],l[sum[i]+n]++;
    int res=0;
    for(int i=0;i<2*n;i++) res+=(l[i]*r[2*n-i]);
    cout<<res<<endl;

    return 0;
}