浙江网站推广运营,网站的pdf目录怎么做的,技术支持东莞网站建设,个人网站开论坛Problem E 发布时间: 2017年6月28日 12:53 最后更新: 2017年6月29日 21:35 时间限制: 1000ms 内存限制: 64M 描述 给定一个长度为n的序列a1, a2, ..., an给定两个整数L, R输出有多少个二元组(x,y),x≤y, 满足L≤∑yixai≤R9104≤n≤105, −109≤ai≤109, −109≤L≤R≤10… Problem E 发布时间: 2017年6月28日 12:53 最后更新: 2017年6月29日 21:35 时间限制: 1000ms 内存限制: 64M 描述 给定一个长度为n的序列a1, a2, ..., an 给定两个整数L, R 输出有多少个二元组(x,y),x≤y, 满足L≤∑yixai≤R 9×104≤n≤105, −109≤ai≤109, −109≤L≤R≤109 输入 第一行三个整数n, L, R, 意义如上所述。 第二行n个整数, 表示序列a。 输出 一个数, 表示答案。 样例输入1 复制 8 -6 6
3 -1 4 -1 5 -9 2 -6 样例输出1 28 题解
要求区间和处于区间[L,R]之间的不同的区间有多少个。
看到要求区间和的问题立刻想到树状数组。
但是现在有两个比较棘手的问题需要处理
1负数下标问题树状数组的下标不能为负数但是我们处理区间和的时候有可能产生负数
2区间和范围太大直接开辟如此大的树状数组肯定会MLE
因此我们考虑这样的方法那就是离散化 我们解决这道题目的总体上的思路就是
for循环sum[1...i]
然后判断有多少个sum[1...j] (j i)使得sum[1....i] - sum[1...j] 在区间[L,R]内
等价于Lsum[i]-sum[j]R 等价于 sum[i]-Rsum[j]sum[i]-L
这样的话我们把sum[i] (1in)进行离散化(最多1e5个值)
我们用二分搜索找出sum[i]-R和sum[i]-L在离散化后的数列中的位置也就是在树状数组中的位置。
然后直接求一个区间和就好了。
注意别忘了for循环体在一开始把sum[i-1]对应的离散值加入到树状数组里面去
代码 #include cstdio
#include iostream
#include algorithm
using namespace std;
typedef long long LL;
const LL MAX 1e5 7;
const int N 1e7 7;
LL a[MAX],b[N];
int n;
LL sm[MAX];
LL dis[MAX];
int mp[MAX];
LL L,R;
inline LL lowbit(int x){return x (-x);
}
LL getsum(int pos){LL res 0;while(pos){res b[pos];pos - lowbit(pos);}return res;
}
void add(int pos,LL val){while(pos N){b[pos] val;pos lowbit(pos);}
}
int main(){scanf(%d%lld%lld,n,L,R);for(int i 1;i n;i){scanf(%lld,a[i]);//a[i] stdi;dis[i-1] sm[i] sm[i-1] a[i];}sort(dis,disn);int k unique(dis,disn) - dis ;//coutkendl;for(int i 1;i n;i)mp[i] lower_bound(dis,disn,sm[i]) - dis 1;LL ans 0;if(a[1] L a[1] R) ans;for(int i 2;i n;i){if(sm[i] L sm[i] R) ans;add(mp[i-1],1);LL x sm[i] - R ;LL y sm[i] - L;int idx lower_bound(dis,disn,x) - dis ;int idy lower_bound(dis,disn,y) - dis ;if(dis[idy] y) idy ;ans getsum(idy) - getsum(idx);//printf(%d\n,getsum(idy) - getsum(idx));}printf(%lld\n,ans);return 0;
}
/*
3 0 0 0 0 0 3 -5 53 -1 4
*/
