Description

给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。

Input Format

第一行为两个正整数n和b ，第二行为1~n 的排列。

Output Format

输出一个整数，即中位数为b的连续子序列个数。

Sample Input

7 4
5 7 2 4 3 1 6

Sample Output

4

Hint

样例解释: {4}, {7,2,4}, {5,7,2,4,3}和{5,7,2,4,3,1,6}

数据规模: N<=100000

【题解】

左右分别统计下，然后乘起来就行了

时间复杂度$O(n)$

# include <stdio.h>
# define FAST __attribute__((optimize("-O2")))
using namespace std;
int n, a[100010], pos, b, l[200010], r[200010], ans=1;
FAST int main() {
	scanf("%d%d",&n,&b);
	for (int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
		if (a[i]==b) pos=i;
	}
	int g=0;
	for (int i=pos+1;i<=n;++i) {
		if(a[i]<b) g++;
		else g--;
		l[g+n]++;
	}
	g=0;
	for (int i=pos-1;i>=1;--i) {
		if(a[i]>b) g++;
		else g--;
		r[g+n]++;
	}
	ans+=l[n]+r[n];
	for (int i=1;i<=2*n-1;++i) {
		ans += (l[i]*r[i]);
	}
	printf("%d\n",ans);
	return 0;
}