【树状数组】【BJOI2016】回转寿司_回转寿司 树状数组

题目告诉我们要求连续区间价值大于等于l，小于等于r的数量，我们考虑使用前缀和维护

以sum[i]为结尾的符合条件的区间数量即sum[i]-r至sum[i]-l这段区间中所包含的前面的前缀和的数量

我们考虑使用数组离散化维护

不把sum[i]-l和sum[i]-r加入也可以，代码中为避免麻烦加入了

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
char c;
int read()
{
	int res=0,bj=1;
	while(c<'0'||c>'9'){if(c=='-') bj=-1; c=getchar();};
	while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48); c=getchar();};
	return res*bj;
}
int n,l,r,N,tree[300005];
long long sum[100005],a[300005],ans;
int find(int x)
{
	int l=1,r=N;
	while(l<r)
	{
		int mid=(l+r+1)>>1;
		if(a[mid]>x) r=mid-1;
		else l=mid;
	}
	return l;
}
void add(int x,int v)
{
	while(x<=N) tree[x]+=v,x+=(x&-x);
}
int ask(int x)
{
	int ans=0;
	while(x) ans+=tree[x],x-=(x&-x);
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&l,&r);
	a[++N]=0;
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read(),a[++N]=sum[i],a[++N]=sum[i]-l,a[++N]=sum[i]-r-1;
	sort(a+1,a+N+1);
	N=unique(a+1,a+N+1)-a-1;
	for(int i=0;i<=n;i++)
	{
		int ls=lower_bound(a+1,a+N+1,sum[i]-r-1)-a;
		int rs=lower_bound(a+1,a+N+1,sum[i]-l)-a;
		ans+=ask(rs)-ask(ls);
		int x=lower_bound(a+1,a+N+1,sum[i])-a;
		add(x,1);
	}
	printf("%lld",ans);
}