题解 P1627 【[CQOI2009]中位数】
zhutier
2018-09-03 21:16:15
以该数为中心，向右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);
}
```
与其他题解的区别大概在于比较懒