题解 P1627 【[CQOI2009]中位数】

· · 题解

以该数为中心，向右for一遍有多少个大于/小于该数的数

大于就sumr++ 小于就--（因为是中位数，大于他的和小于他的数的数量一样）

然后每次以sumr为下标的数++

因为sumr可能小于零

并且我比较懒

所以就开了一个map

万能的map！

所以就直接mp[sumr]++;

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
map<int,int> mp;
int n,b,a[100005],q,suml,sumr;
long long ans;
int main(){
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==b) q=i;
    }
    for(int j=q;j<=n;j++){
        if(a[j]>b) sumr++;
        if(a[j]<b) sumr--;
        mp[sumr]++;
    }
    for(int i=q;i>=1;i--){
        if(a[i]>b) suml++;
        if(a[i]<b) suml--;
        ans+=mp[0-suml];
    }
    printf("%lld",ans);
}

与其他题解的区别大概在于比较懒