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