[Codeforces Round #496 (Div. 3)] E2 Median on Segments (General Case Edition)

        题目大意：给定一个整数序列\(\{a_n\}\)，求中位数为m的连续子序列个数（如果取出的子序列长度为偶数，则中位数取较小的那个）。其中\(n \leq 200000,a_i \leq 200000\)。

        题解：数字的具体大小显然是没有关系的，只有小于m、等于m、大于m三种情况，于是可以由此当作-1,0,1三个数来看。

        考虑区间和，我们会发现由于等于m的数值取0,导致无法通过区间和来判断中位数具体是多少。

        一种考虑是判断每一个m是否是中位数，其左边的m取-1,自己取0,右边的m取1，这样区间和=0或1的满足条件，但这样具体求和的时候非常麻烦。

        标算是通过计算f(x)表示中位数大于等于x的区间个数来算，答案就是\(f(m+1)-f(m)\)。f(x)的计算便会容易很多。只需要将所有小于x的数当作-1，大于等于x的数当作1，这样区间和大于0的都满足条件。

        （Div3的题目写不出来真的是菜死了）

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;

int a[maxn];
int cnt[maxn<<1];
int n,m;
long long res;

long long Solve(int c)
{
	memset(cnt,0,sizeof(cnt));
	int *s=cnt+maxn;
	long long res=0;
	s[0]=1;
	int nowsum=0,p=0;
	for (int i=1;i<=n;i++)
	{
		int x=a[i]>=c?1:-1;
		if (x==1) nowsum+=s[p];
		else nowsum-=s[p-1];
		s[p+=x]++;
		res+=nowsum++;
	}
	return res;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	printf("%I64d\n",Solve(m)-Solve(m+1));
	return 0;
}