发现都是权值线段树+动态开点的题解,交个短得多的 CDQ 分治(那个::l
和::r
是不小心变量重名了引用的全局变量)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+50;
int n;
ll l,r;
int a[N];
ll s[N],w[N];
ll ans;
void merge_sort(int l,int r) {
if(l==r) return;
int mid=l+r>>1;
merge_sort(l,mid),merge_sort(mid+1,r);
int head=l,tail=l-1;
for(int i=mid+1;i<=r;++i) {
while(s[i]-s[tail+1]>=::l&&tail+1<=mid) tail++;
while(s[i]-s[head]>::r&&head<=mid) head++;
ans+=tail-head+1;
}
int i=l,j=mid+1,cnt=0;
while(i<=mid&&j<=r) {
if(s[i]<s[j]) w[++cnt]=s[i++];
else w[++cnt]=s[j++];
}
while(i<=mid) w[++cnt]=s[i++];
while(j<=r) w[++cnt]=s[j++];
for(int i=l;i<=r;++i) s[i]=w[i-l+1];
}
int main() {
scanf("%d%lld%lld",&n,&l,&r);
for(int i=1;i<=n;++i) scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
merge_sort(0,n);
printf("%lld\n",ans);
return 0;
}