3 seconds
256 megabytes
standard input
standard output
You are given a permutation p1,p2,…,pnp1,p2,…,pn. A permutation of length nn is a sequence such that each integer between 11 and nn occurs exactly once in the sequence.
Find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.
The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used.
For example, if a=[4,2,7,5]a=[4,2,7,5] then its median is 44 since after sorting the sequence, it will look like [2,4,5,7][2,4,5,7] and the left of two middle elements is equal to 44. The median of [7,1,2,9,6][7,1,2,9,6] equals 66 since after sorting, the value 66 will be in the middle of the sequence.
Write a program to find the number of pairs of indices (l,r)(l,r) (1≤l≤r≤n1≤l≤r≤n) such that the value of the median of pl,pl+1,…,prpl,pl+1,…,pr is exactly the given number mm.
The first line contains integers nn and mm (1≤n≤2⋅1051≤n≤2⋅105, 1≤m≤n1≤m≤n) — the length of the given sequence and the required value of the median.
The second line contains a permutation p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n). Each integer between 11 and nn occurs in pp exactly once.
Print the required number.
5 4
2 4 5 3 1
4
5 5
1 2 3 4 5
1
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
48
In the first example, the suitable pairs of indices are: (1,3)(1,3), (2,2)(2,2), (2,3)(2,3) and (2,4)(2,4).
题意：给出n个数，中位数m，求在这n个数中的任意区间内中位数是n的个数，区间个数是偶数的时候去左边的为 中位数
解题思路：刚开始我以为这是主席树的模板题，第k大,后来听别人说不用这么复杂，因为是n个数互不重复1-n，因为要求的区间里面肯定包含了m，所以我们先求出m的位置，然后我们仔细想
可以得知在这个区间里面要使中位数是m的话，奇数区间大于m的个数与小于m的个数是一样的，偶数区间是大于m的个数比小于m的个数多1，所以我们用map记录比m大和小的个数，我们先从
m的位置从右边遍历求出区间大于小于m的情况，用map 存大于m和小于m的差值，这样比较方便，比如mp[0]=1,说明右边大于m和小于m的区间个数相等的区间有1个，比如mp[-1]=2,说明右边
大于m比小于m少一个的区间个数有2个，以此类推，然后我们再此遍历左边，如果左边大于m的个数是1的话，奇数区间那么我就要右边小于m的个数为1，也就是mp[-1],偶数区间就要右边大于m
小于m个数相等，也就是mp[0],从而推出式子 cnt记录大于小于m的个数 sum=sum+mp[-cnt]+mp[1-cnt];
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main()
{
map<ll,ll> mp;
ll m,n,a[];
cin>>n>>m;
int pos;
for(int i=;i<n;i++)
{
cin>>a[i];
if(a[i]==m)
pos=i;
}
int cnt=;
for(int i=pos;i<n;i++)
{
if(a[i]>m) cnt++;
if(a[i]<m) cnt--;
mp[cnt]++;
}
ll sum=;
cnt=;
for(int i=pos;i>=;i--)
{
if(a[i]>m) cnt++;
if(a[i]<m) cnt--;
sum=sum+mp[-cnt]+mp[-cnt];
}
cout<<sum;
}