0pts求吊
查看原帖
0pts求吊
754467
f_hxr_楼主2023/9/14 17:34

rt。。。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL N,L,R,sum[200005],ans;
void CDQ(LL l,LL r){
	if(l==r)return;
	LL mid=(l+r)>>1;
	CDQ(l,mid);CDQ(mid+1,r);
	sort(sum+l,sum+mid+1);
	sort(sum+mid+1,sum+r+1);
	LL head=l,tail=l-1;
	for(int i=mid+1;i<=r;i++){
		while(tail+1<=mid&&sum[tail+1]+L<=sum[i])tail++;
		while(head<=mid&&sum[head]+R<sum[i])head++;
		ans+=max(0LL,tail-head+1);
	}
}
int main(){
	cin>>N>>L>>R;
	for(int i=1,t;i<=N;i++)
		cin>>t,sum[i]=sum[i-1]+t;
	CDQ(1,N);
	cout<<ans;
	return 0;
}
2023/9/14 17:34
加载中...