【题解】中位数图

每日一题终于来了一个简单的题了！！！

思路：
首先这是一个排列，也就是说每个数只出现一次。我们把要找到的数的位置记为pos，对于pos右边，从pos+1到n扫一遍，同时用map存下来一个值：从pos+1到i这段区间里面比b大和比b小的差值的个数（比如2 3 4这里面差值是-3，2 5 6的差值是1，也就是说比b大就++，小就--，然后mp[count]++）。左边也同理存一下。

有什么用呢？我们只需要扫一下左边（或者右边）的map存放值，跟另一边的负存放值，答案加上这两个存放值的个数就好了。
比如：对于左边的mapl[3]，那么我们需要找到右边有多少个mapr[-3]，然后答案就需要加上mapl[3]*mapr[-3]。
最后记得在扫的过程中，如果差值出现0就ans直接++。

代码：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=5e5+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

int a[maxn];

int main(){
    map<int,int> ml,mr;
    int pos=0;
    int n,b;
    scanf("%d%d",&n,&b);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        if(a[i]==b) pos=i;
    }
    int tmp=0;ll ans=1;
    for(int i=pos+1;i<=n;i++){
        if(a[i]>b) tmp++;
        else tmp--;        
        if(tmp==0) ans++;
        mr[tmp]++;
    }
    tmp=0;
    for(int i=pos-1;i>=1;i--){
        if(a[i]>b) tmp++;
        else tmp--;
        if(tmp==0) ans++;
        ml[tmp]++;
    }
    for(auto it:ml){
        ans+=ml[it.fs]*mr[-(it.fs)];
    }
    printf("%lld",ans);
    return 0;
}