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)
题意：给你n个数和一个m，为你有多少个l，r，即l到r区间，有多少个这样的区间，使m成为这个区间序列的中位数。
思路： 把m的左边序列做一下预处理，利用前缀和处理出大于m的个数与小于m的个数之差，即小于m的个数减去大于m的个数，（可以把大于m的变成1，小于m的变成-1，然后计和）然后因为当区间数是偶数的时候，他要取得是中间两个数右边的一个，这个时候当大于m的个数 = 小于m的个数 + 1的也应该成立 ，所以数列左侧的答案，有mm[0]和mm[-1]，然后遍历右边，当序列的大于m的个数减去小于m的个数的时候，看看map里面的mm是否存在这个差值，如果存在的话，左右的差值是不是就可以抵消了，还有就是偶数的情况，所以我们要在考虑两个相差1的时候（还有就是结果要long long）
代码如下：
#include <bits/stdc++.h>using namespace std;const int maxn = 1e6 + 100;
int n,m;
int a[maxn];
int d[maxn];
map<int,int>mm;
int s[maxn];
int main() {while(~scanf("%d%d",&n,&m)) {mm.clear();int m1 = 0,m2 = 0;memset(d,0,sizeof(d));int id;mm[0] = 1;for(int i = 0; i < n; i++) {scanf("%d",&a[i]);if(a[i] == m) id = i;if(a[i] < m) d[i] = -1;else if(a[i] > m) d[i] = 1;}s[0] = d[0];for(int i = 1; i < n; i++)s[i] = s[i - 1] + d[i];for(int i = 0; i < n; i++)if(i < id)mm[-(s[id] - s[i - 1])]++;m1 = 0,m2 = 0;long long ans = mm[-1] + mm[0]; for(int i = id + 1; i < n; i++) if(a[i] < m) m1++;else if(a[i] > m) m2++;ans += mm[m2 - m1] + mm[m2 - m1 - 1]; cout << ans << endl;}return 0;
}