[CQOI2009]中位数图

因为只要个数所以可以大于b的记作1,小于b的记作-1,然后如果b的左右相加之和为0,则算成立
如: 写成 ,如果一个区间要成立的前提就是b左右两边的值相加为0,那么如果左边值相加为-2,右边值相加为2,并且b的左右两边的数的个数是大于2的,那么里面必定存在(-1,1)情况,所以就是可以确保求出得长度为奇数
然后分情况讨论
左区间位于b的位置
右区间位于b的位置
左右区间都不在b的位置
针对前两种情况可以直接进行从b位置进行左右求和,如果和为0,ans++
针对第三种情况,可以记录从b开始向左求和时到每一位的值,然后记录每一种值得数量
然后b向右求和,每到一位求出得值,ans+=b得左边出现其乘以-1的个数
最后ans++,因为对于b本身也算一种情况
时间复杂度:

#include<bits/stdc++.h>
using namespace std;
int n,b,a[100005],m[100005],ans=1,j;
int main()
{
    cin>>n>>b;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]<b) a[i]=-1;
        if(a[i]>b) a[i]=1;
        if(a[i]==b) j=i;
    }
    int c=0;
    for(int i=j-1;i>=0;i--)
    {
        c+=a[i];
        m[c+n]++;
        if(!c) ans++;
    }
     c=0;
    for(int i=j+1;i<n;i++)
    {
        c+=a[i];
        ans+=m[n-c];
        if(c==0) ans++;
    }
    cout<<ans;
}