一个大于b的数和一个小于b的数可以互相抵消,所以我们用1和-1表示。

从b向两边扩展,left[i]表示b左边抵消后有i个数比b小的可能数,right[i]表示b右边抵消后有i个数比b大的可能数。

ans=sigma(left[i]*right[i]).

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std; #define N 200010 int n,b,k; int ans; int a[N];
int l[N],r[N],sum[N]; int main()
{
scanf("%d%d",&n,&b);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]==b)
k=i,a[i]=0;
else
a[i]=a[i]>b ? 1 : -1;
}
l[n]=1;
r[n]=1;
for (int i=k-1;i>=1;i--)
{
sum[i]=sum[i+1]+a[i];
l[sum[i]+n]++;
}
for (int i=k+1;i<=n;i++)
{
sum[i]=sum[i-1]+a[i];
r[sum[i]+n]++;
}
for (int i=1-n;i<=n-1;i++)
ans+=l[i+n]*r[(n<<1)-(i+n)];
printf("%d",ans);
return 0;
}

  

最新文章

  1. WCF学习之旅—TCP双工模式(二十一)
  2. couchDB文档
  3. Javascript笔记----实现Page页面右下角置顶按钮.
  4. 阿里云服务器 FTP配置图文教程和添加两个FTP站点
  5. java 文件读取大全
  6. rabbitMQ入门
  7. MLlib 卡方检验
  8. 软件体系结构经典问题——KWIC的分析和解决
  9. JSthis对象
  10. Android复制iPhone日期和时间选择器
  11. OpenStack路: OpenStack建筑设计指南 - 概要(摘录和翻译)
  12. 第18章 备忘录模式(Memento Pattern)
  13. grep 、find 、tree 新发现
  14. springboot之fastjson
  15. vue源码阅读(一)
  16. Java基础回顾Application(一)
  17. 将Myeclipse非maven项目,导入到IDEA
  18. libgdx判断actor与circle是否重叠
  19. HDU 3480 - Division - [斜率DP]
  20. FileStream 和StreamWriter 一起用时

热门文章

  1. A10. JVM 对象
  2. 在 VS2015+EF6.0中使用Mysql 遇到的坑
  3. (十二)python3 迭代器
  4. Python面试快问快答,理论要的就是速度与精准,Python面试题No2
  5. jmeter 接口测试
  6. JavaScript - 如果...没有方法(xjl456852修改)
  7. bash shell &amp; front-end &amp; auto publish &amp; auto deploy
  8. hdu3592(差分约束) (线性)
  9. 【bzoj3747】[POI2015]Kinoman - 线段树(经典)
  10. Django开发:(1)django基础 &amp; url控制器