[Codeforces Round #466 (Div. 2)][Codeforces 940F] Machine Learning
[Educational Codeforces Round 41] E Tufurama

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

Zarxdy34 posted @ 2018年7月12日 16:00 in Codeforces with tags 容斥 , 11 阅读

        题目大意:给定一个整数序列\(\{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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top