首先我们要找到 $K$ 的位置 $p$

然后从 $p$ 分别向左右来扩展，记录下比 $p$ 大和小的个数

因为若 $K$ 为中位数，那么这个区间内比 $K$ 大的和比 $K$ 小的个数一定相等

那我们可以先把左边大的和小的哈希一下并用map存下来出现过多少次

然后再从 $p$ 枚举到 $n$ ，将这个大小个数也哈希，然后再统计

注意奇数位置和偶数位置的区别

#include<iostream>
#include<cstdio>
#include<map>
#define int long long
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int T=1,n,k,p,ans=0;
int a[N];
int r[N][2],l[N][2];//0->max,1->min
map<string,int> mpj,mpo;
bool Test_MLE_end;
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c-'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("A.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//  Don't forget!

}
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	T=reads();
	while(T--){
		clr();
		n=reads(),k=reads();
		for(int i=1;i<=n;i++){
			a[i]=reads();
			if(a[i]==k) p=i;
		}
		for(int i=p+1;i<=n;i++){
			r[i][0]=r[i-1][0],r[i][1]=r[i-1][1];
			if(a[i]>a[p]) r[i][0]++;
			else r[i][1]++;
		}
		for(int i=p-1;i>=1;i--){
			l[i][0]=l[i+1][0],l[i][1]=l[i+1][1];
			if(a[i]>a[p]) l[i][0]++;
			else l[i][1]++;
		}
		for(int i=1;i<=p;i++){
			int t=min(l[i][0],l[i][1]),x=l[i][0]-t,y=l[i][1]-t;
			string s="";
			for(int j=1;j<=5;j++){
				s=(char)(y%10+'0')+s;
				y/=10;
			}
			for(int j=1;j<=5;j++){
				s=(char)(x%10+'0')+s;
				x/=10;
			}
			if(i&1) mpj[s]++;
			else mpo[s]++;
		}
		for(int i=p;i<=n;i++){
			int t=min(r[i][0],r[i][1]),x=r[i][0]-t,y=r[i][1]-t;
			string s="";
			for(int j=1;j<=5;j++){
				s=(char)(x%10+'0')+s;
				x/=10;
			}
			for(int j=1;j<=5;j++){
				s=(char)(y%10+'0')+s;
				y/=10;
			}
			if(i&1) ans+=mpj[s];
			else ans+=mpo[s];
		}
		printf("%lld\n",ans);
	}
	return 0;
}

统计两个前缀mx,mi，分别是比m小的和比m大的个数，开桶记录这两个值的差，当我们希望m是中位数时区间 [i,j] 显然有 $mx_j-mx_{i-1}=mi_j-mi_{i-1}$，移项可得

在 m 之前记录mx-mi的个数，在m之后统计答案，注意边界。

我的挂分原因 const int N=1e5

题意

给定$n$个数分别为$1-n$

问长度为奇数的区间，且该区间的中位数为$k$的方案数

做法

我们将大于k的值换为1，小于k的换成-1，等于的换成0

这样问题就转换为一定包含k位置且区间和为0的区间数

因为我们一定要包含那个a[i]为0的数，所以一定满足长度为奇数

code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n, k, st;

int a[N], mp[N];

void read(){
	cin >> n >> k;
	for(int i = 1;i <= n; i++){
		cin >> a[i];
		a[i] = a[i] > k ? 1 : a[i] == k ? 0 : -1;
	}
	for(int i = 1;i <= n; i++){
		if(a[i] == 0) st = i;
		a[i] = a[i-1] + a[i];
	}
	return ;
}

void compute(){
	int ans = 0;
	mp[n] = 1;
	for(int i = 1;i <= n; i++){
		if(i >= st){
			ans += mp[a[i]+n];
		}
		else mp[a[i]+n]++;
	}
	cout << ans;
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}