http://codeforces.com/contest/1005/problem/E1 题目
https://blog.csdn.net/haipai1998/article/details/80985281 原博客
对样例1：
5 4
2 4 5 3 1
m=4，所以下标pos=2； 从pos往右遇到比m大的就cnt++,遇到小的就cnt--： 刚开始cnt=0; mp[cnt]++
于是从pos开始到 n： mp[0]=1, mp[1]=1, mp[0]=2 , mp[-1]=1;
接下来从pos向左， 遇到比m大的就cnt-- ，遇到比小的就cnt++ ， 刚开始cnt=0
因为n为偶数时m要排在n/2 ，n为奇数时m要排在n/2+1；
所以 ans += mp[cnt] + mp[cnt+1] 比如i=pos时候，此时cnt=0, ans+=mp[0]+mp[1] （偶数的情况加上奇数的情况）
i=pos-1，即cnt=1，a[i]=2的时候，ans+=mp[1]+mp[2] （mp[1]即加到5的位置）
1 #include<iostream> 2 #include<cstdio> 3 #include <cctype> 4 #include<algorithm> 5 #include<cstring> 6 #include<cmath> 7 #include<string> 8 #include<cmath> 9 #include<set> 10 #include<vector> 11 #include<stack> 12 #include<queue> 13 #include<map> 14 using namespace std; 15 #define ll long long 16 #define mem(a,x) memset(a,x,sizeof(a)) 17 #define se second 18 #define fi first 19 const int INF= 0x3f3f3f3f; 20 const int N=2e5+5; 21 22 int n,m,pos,a[N]; 23 map<int,ll> mp; 24 25 int main() 26 { 27 cin>>n>>m; 28 for(int i=1;i<=n;i++){ 29 scanf("%d",&a[i]); 30 if(a[i]==m) pos=i; 31 } 32 int num=0,cnt=0; 33 for(int i=pos;i<=n;i++) 34 { 35 if(a[i]>m) cnt++; 36 if(a[i]<m) cnt--; 37 mp[cnt]++; 38 } 39 num=0,cnt=0; 40 ll ans=0; 41 for(int i=pos;i>=1;i--) // 2 4 5 3 1 42 { 43 if(a[i]<m) cnt++; 44 if(a[i]>m) cnt--; 45 ans+=mp[cnt]+mp[cnt+1]; 46 } 47 cout<<ans; 48 }
Codeforces #496 E1. Median on Segments (Permutations Edition)
原文：https://www.cnblogs.com/thunder-110/p/9482094.html