思路楼下都说了,简单总结下
1.只关心相对大小,所以数字可以转为1,-1,0。要求覆盖b位置的总和为0的连续子序列数量
2.用部分和,只要求左右部分和相等的对数
3.由于部分和的范围是有界的,使用计数排序即可,复杂度O(n)
下面是比较短的代码实现
```cpp
#include <iostream>
#define N 100005
using namespace std;
long long n,b,ans,c[2][2*N];
int main () {
cin>>n>>b; c[0][n]=1;
for (long long i=0,a,s=n,isRight=0;i<n;i++){
cin>>a;
if (a!=b) s+=a>b?1:-1;
c[isRight|=a==b][s]++;
}
for (long long i=0;i<2*n;i++,ans+=c[0][i]*c[1][i]);
cout<<ans<<endl;
return 0;
}
```