题目描述
给出一串数字,问中位数大于等于X的连续子串有几个。(这里如果有偶数个数,定义为偏大的那一个而非中间取平均)
核心思路
当我们遇到中位数题目时,一个很平常的处理就是把大于x的赋值成1,小于x的赋值成0,然后预处理初前缀和
然后我们如果想找到一个符合题意的字串,就要满足\(sum[r]-sum[l-1]>0\)
不妨进行转化,可以得到:\(sum[r]>sum[l-1]\),这题就很显然是用总方案数求逆序对了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
long long n,x,num;
long long ans;
long long a[100001];
long long tmp[100001];
void merge_sort(int l,int r){
if(l>=r) return ;
int mid=(l+r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int k=0;
int i=l,j=mid+1;
while(i<=mid && j<=r){
if(a[i]<=a[j]) tmp[++k]=a[i++];
else tmp[++k]=a[j++],ans+=(mid-i+1);
}
while(i<=mid) tmp[++k]=a[i++];
while(j<=r) tmp[++k]=a[j++];
for(int i=l,j=1;i<=r;i++,j++) a[i]=tmp[j];
}
int main(){
scanf("%lld%lld",&n,&x);
for(int i=1;i<=n;i++)
scanf("%lld",&num),
a[i]=a[i-1]+(num>=x?1:-1);
merge_sort(0,n);
printf("%lld",n*(n+1)/2-ans);
return 0;
}
注意几个细节:
1.merge_sort或者线段树求逆序对时,因为sum[l-1],所以要从0开始合并
2.用long long输出