Median on Segments (Permutations Edition)

​​E1. Median on Segments (Permutations Edition)​​

參考：​​CF1005E1 Median on Segments (Permutations Edition) 思維​​

中位數為m的條件為，在那一段中，小于 m 的數的個數為 x 個，大于 m 的數有 y 個，要滿足條件​

​x==y||x==y-1​

​。

因為不可能每一次都去統計有多少個大于的多少個小于的，是以我們要預處理一下，借此來降低複雜度

map<int,int> ma;

int cnt=0;

for(int i=pos;i>=1;--i)

{

if(p[i]<m) cnt--;

else if(p[i]>m) cnt++;

ma[cnt]++;

}

// Created by CAD on 2020/1/11.
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=2e5+5;
int p[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    int pos;
    for(int i=1;i<=n;++i)
    {
        cin>>p[i];
        if(p[i]==m) pos=i;
    }
    map<int,int> ma;
    int cnt=0;
    for(int i=pos;i>=1;--i)
    {
        if(p[i]<m) cnt--;
        else if(p[i]>m) cnt++;
        ma[cnt]++;
    }
    ll ans=0;  cnt=0;
    for(int i=pos;i<=n;++i)
    {
        if(p[i]<m) cnt++;
        else if(p[i]>m) cnt--;
        ans+=ma[cnt]+ma[1+cnt];
    }
    cout<<ans<<endl;
    return 0;
}