E1. Median on Segments (Permutations Edition)[如何判断无序中位数]

E1. Median on Segments (Permutations Edition)

题意:一个长为n的打乱的全排列,给定m,问包含m的区间中,有多少个区间的中位数是m

思路:假设m的位置为pos,先处理出[pos+1~n]中到达每个点的,比m大和比m小的差值.  假设一个区间可以,那么有 大于m的数-小于m的数=1 or 0 那么. 再从[pos-1,1]处理一遍,就处理出所有的答案

#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=1e9+7;
int a[N],sum1[N],sum2[N];
map<int,ll> mp;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n,m,pos;
    cin >>n>>m;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(a[i]==m) pos=i;
    }
    int now=0;
    mp[now]++;
    for(int i=pos+1;i<=n;i++){
        if(a[i]>m)  now++;
        else    now--;
        mp[now]++;
    }
    now=0;
    ll ans=mp[0]+mp[1];
    for(int i=pos-1;i>=1;--i){
        if(a[i]<m)  now++;
        else    now--;
        ans+=mp[now]+mp[now+1];
    }
    cout << ans << endl;

    return 0;
}

最后

以上就是热情河马为你收集整理的E1. Median on Segments (Permutations Edition)[如何判断无序中位数]的全部内容，希望文章能够帮你解决E1. Median on Segments (Permutations Edition)[如何判断无序中位数]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。