自动搬运

查看原文

来自洛谷，原作者为

	zhutier 窝窝头，一块钱四个，嘿嘿

搬运于2025-08-24 21:27:16，当前版本为作者最后更新于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);
} 

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