赞
踩
算法:裸树状数组/裸线段树
难度:(NOIP-)
- 设s[i]为前缀和,差分,把序列和转化为前缀相减,即选出满足L≤s[x]−s[y]≤R的x>y的数个数。
- 那么我们枚举x,即可得到y的范围,二分找以前的满足条件的yy的个数(lowerbound&&upper_bound)。可以维护1到当前位置树状数组,在树状数组中查询个数,最后再将该数加入到树状数组中。但是数据范围大,所以需要离散化。
- 时间复杂度O(nlogn)
代码如下:
- //不开long long 见祖宗!
- #include <cstdio>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <algorithm>
- #include <cmath>
- #include <queue>
- #define ll long long
- #define N 100005
- using namespace std;
- ll a[N],sum[N],c[N];
- ll n,l,r;
- int lowbit(int x)
- {
- return x & (-x);
- }
- void add(int x)
- {
- while(x<=n)
- {
- c[x]++;
- x+=lowbit(x);
- }
- }
- int query(int x)
- {
- int ret=0;
- while(x)
- {
- ret+=c[x];
- x-=lowbit(x);
- }
- return ret;
- }
- int main()
- {
- scanf("%lld%lld%lld",&n,&l,&r);
- for(int i = 1;i <= n;i++)
- {
- scanf("%lld",&a[i]);
- sum[i]=sum[i-1]+a[i];
- a[i]=sum[i];
- }
- sort(a+1,a+n+2);//多加一个sum[0],防止lowerbound时,数组越界。
- ll ans=0;
- for(ll i = 0;i <= n;i++)
- {
- ans+=query(upper_bound(a+1,a+n+2,sum[i]-l)-a-1)-query(lower_bound(a+1,a+n+2,sum[i]-r)-a-1);
- add(lower_bound(a+1,a+n+2,sum[i])-a);
- }
- printf("%lld\n",ans);
- return 0 ;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。