巧妙维护与中位数有关问题的信息

对于中位数的题，可以思考把大于它的数标记为1，小于的数标记为-1，等于的标记为0

#include <bits/stdc++.h>

using namespace std;

int arr[100050];
int pl[100050];
int pr[100050];
int main(void)
{
	int n,f,pos;
	scanf("%d%d",&n,&f);
	for (int i=1;i<=n;i++) 
	{
		scanf("%d",&arr[i]);
		if (arr[i]<f) arr[i]=-1;
		else if (arr[i]>f) arr[i]=1;
		else if (arr[i]==f) arr[i]=0,pos=i;
	}
	int k1=0,k2=0;
	for (int i=pos-1;i>=1;i--)
	{
		++k1;
		pl[k1]=pl[k1-1]+arr[i];
	}
	for (int i=pos+1;i<=n;i++)
	{
		++k2;
		pr[k2]=pr[k2-1]+arr[i];
	}
	//printf("%d %d\n",k1,k2);
	int ans=0;
	for (int i=0;i<=k1;i++)
	{
		for (int j=0;j<=k2;j++)
		{
			if (pl[i]==-pr[j]) ans++;
		}
		//printf("%d\n",ans);
	}
	printf("%d\n",ans);
}