/*
给定一个数组,要求和小于t的段落总数
求前缀和
dp[i]表示以第i个数为结尾的小于t的段落总数,sum[i]-sum[l]<t;
sum[i]-t<sum[l],所以只要找到满足条件的sum[l]数量即可
将sum排序,每次找到sum[i]-t的排名,大于它的就是l的数量
*/
#include<bits/stdc++.h> using namespace std;
#define ll long long
#define maxn 200005
ll tmp[maxn],n,a[maxn],t,sum[maxn],ans;
ll bits[maxn];
void add(int x,int val){
for(int i=x;i<=n+;i+=i&-i)
bits[i]++;
} ll query(int x){
ll ans = ;
for(int i=x;i>;i-=i&-i)
ans += bits[i];
return ans;
} int main(){
cin>>n>>t;
memset(bits,,sizeof bits);
for(int i=;i<=n;i++)cin>>a[i];
for(int i=;i<=n;i++)sum[i]=sum[i-]+a[i];
for(int i=;i<=n;i++)tmp[i]=sum[i]; sort(tmp,tmp++n);//带着0排序
//add(0,1); for(int i=;i<=n;i++){
int pos=lower_bound(tmp,tmp+n+,sum[i-])-tmp+;
add(pos,);
pos=upper_bound(tmp,tmp+n+,sum[i]-t)-tmp;
ans+=i-query(pos);
}
printf("%lld\n",ans);
}

最新文章

  1. spring ioc
  2. .NET/ASP.NETMVC 大型站点架构设计—迁移Model元数据设置项(自定义元数据提供程序)
  3. 利用 async &amp; await 的异步编程
  4. 第8章 用户模式下的线程同步(3)_Slim读写锁(SRWLock)
  5. java https tomcat 单双认证(含证书生成和代码实现) 原创转载请备注,谢谢O(∩_∩)O
  6. unity,将camera设为don&#39;t clear在android上会显示不正常
  7. 搭建Nginx(负载均衡)+Redis(Session共享)+Tomcat集群
  8. HDU 3966 Aragorn&#39;s Story (树链点权剖分,成段修改单点查询)
  9. Wildfly8 更改response header中的Server参数
  10. HRBUST 1987 逃课的孩子
  11. [编程题] 最大的LeftMax与rightMax之差绝对值
  12. Flipping Game(枚举)
  13. 【精编重制版】JavaWeb 入门级项目实战 -- 文章发布系统 (第二节)
  14. HDU4624 Endless Spin 【最大最小反演】【期望DP】
  15. 第一条:了解Objective-C语言的起源
  16. Linux错误代码含义
  17. 【NOIP 2015】Day2 T3 运输计划
  18. 非常好的一个CentOS 6.2 apache 2.4.2 编译教程
  19. hdu2579之BFS
  20. .net core 的优点

热门文章

  1. python - 条件语句/循环语句/迭代器
  2. SpringBoot文件上传大小设置(yml中配置)
  3. Shell基础总结
  4. FAT文件系统规范v1.03学习笔记---1.保留区之启动扇区与BPB
  5. Go语言中的struct tag
  6. pt-table-sync 使用方法【转】
  7. HTML5实现全屏
  8. Cassandra索引详解
  9. Multisim 经典学习教程Step by Step
  10. maven:打包时报错,报&rsquo;找不到符号&rsquo;