题意

给定 1 1 1 个 1 ∼ n 1\sim n 1∼n 的排列和一个数 b b b，保证 b b b 是 1 ∼ n 1\sim n 1∼n 中的一个整数，求以 b b b 为中位数的长度为奇数的连续子序列个数。

分析

首先想到的是暴力求解，枚举所有包含 b b b 的长度为奇数的连续子序列，记录答案，这个思路明显会超时。

进一步优化，考虑一个长度为奇数的连续子序列如果它的中位数是 b b b，那么其中大于 b b b 的数和小于 b b b 的数一定是一样多的。以 b b b 为中心，分别向前后枚举，如果大于 b b b 的数和小于 b b b 的数数量相等，就记录答案，这个思路比上一个有所优化，但依然无法通过所有测试点。

再进一步优化，只从 b b b 向前枚举， b b b 之后的部分进行预处理，并且不记录大于 b b b 的数和小于 b b b 的数的数量，而是记录大于 b b b 的数和小于 b b b 的数的数量差，如果 b b b 之前的数量差与 b b b 之后的数量差相加为零，则这一部分能够构成一个以 b b b 为中位数的长度为奇数的连续子序列，这个思路可以通过所有测试点。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,m,a[1000005],t,xc,dc,ans,xxc,ddc;
map<long long,long long>p;
int main()
{
   
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
   
		cin>>a[i];
		if(a[i]==m)t=i;//找到m的位置。
	}
	xxc=ddc=xc=dc=0;
	for(int i=t+1;i<=n;i++)//预处理
	{
   
		if(a[i]<m)xxc++;
		else ddc++;
		p[xxc-ddc]++;
	}
	for(int i=t;i>0;i--)
	{
   
		if(i!=t)
		{
   
			if(a[i]<m)xc++;
			else dc++;
		}
		if(xc==dc)ans++;
		ans=ans+p[-1*(xc-dc)];
	}
	cout<<ans;
	return 0;
}