30pts求调
查看原帖
30pts求调
378914
吴明事楼主2022/11/12 15:47
#include<bits/stdc++.h>
using namespace std;
int n,L,R,ans;
int a[100005],d[3*100005],_d[3*100005],tr[400005];
int sum[100005];
int cnt;
void update(int k,int l,int r,int s){
	if(l==r&&l==s){
		tr[k]++;
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)update(k<<1,l,mid,s);
	else update(k<<1|1,mid+1,r,s);
	tr[k]++;
}
int search(int k,int l,int r,int sl,int sr){
//	cout<<k<<' '<<l<<' '<<r<<' '<<sl<<' '<<sr<<'\n';
	if(sr==r&&sl==l)return tr[k];
	int mid=(l+r)>>1;
	if(sr<=mid)return search(k<<1,l,mid,sl,sr);
	else if(sl>mid)return search(k<<1|1,mid+1,r,sl,sr);
	else return search(k<<1,l,mid,sl,mid)+search(k<<1|1,mid+1,r,mid+1,sr);
}
void disc(){
	for(int i=0;i<n;i++){
		d[i*3+1]=sum[i+1]-R;
		d[i*3+2]=sum[i+1];
		d[i*3+3]=sum[i+1]-L;
	}
	sort(d+1,d+3*n+1);
}
int main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	cin>>n>>L>>R;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	disc();
	cnt=unique(d+1,d+3*n+1)-d-1;
	update(1,1,cnt,lower_bound(d+1,d+cnt+1,0)-d);
	for(int i=1;i<=n;i++){
		int l=lower_bound(d+1,d+cnt+1,sum[i]-R)-d;
		int r=lower_bound(d+1,d+cnt+1,sum[i]-L)-d;
		ans+=search(1,1,cnt,l,r);
		update(1,1,cnt,lower_bound(d+1,d+cnt+1,sum[i])-d);
	}
//	for(int i=1;i<=cnt;i++)cout<<d[i]<<' ';
//	cout<<'\n';
	cout<<ans;
	return 0;
}

record

2022/11/12 15:47
加载中...