luogu P5459 [BJOI2016]回转寿司_n等于xi+yi+zi

题面传送门
题目要求有多少个$i，j$使的$l\le \sum _{k=i}^j{a}_i\le r$
用前缀和搞一下，变成$l\le q_j-q_{i-1}\le r$
再变换一下，变成$q_j-r\le q_{i-1}\le q_j-l$
然后动态开点线段树或者平衡树一搞就好了。
代码实现:

#include<cstdio>
using namespace std;
long long n,m,k,x,y,z,a[100039],tot=1;
long long q[100039],ans,l,r;
struct tree{int l,r,sum;}f[5000039];
inline void get(long long x,long long l,long long r,int now){
	if(l==r){f[now].sum++;return;}
	long long m=(l+r)>>1;
	if(x<=m){
		if(!f[now].l) f[now].l=++tot;
		get(x,l,m,f[now].l);
	}
	else{
		if(!f[now].r) f[now].r=++tot;
		get(x,m+1,r,f[now].r);
	}
	f[now].sum=f[f[now].l].sum+f[f[now].r].sum;
}
inline int find(long long x,long long y,long long l,long long r,int now){
	if(x<=l&&r<=y) return f[now].sum;
	long long m=(l+r)>>1;
	int fs=0;
	if(x<=m&&f[now].l) fs+=find(x,y,l,m,f[now].l);
	if(y>m&&f[now].r) fs+=find(x,y,m+1,r,f[now].r);
	return fs;
}
int main(){
	//freopen("1.in","r",stdin);
	register int i;
	scanf("%lld%lld%lld",&n,&l,&r);
	for(i=1;i<=n;i++) scanf("%lld",&a[i]),q[i]=q[i-1]+a[i];
	get(0,(long long)-1e10-1e9,(long long)1e10,1);
	for(i=1;i<=n;i++){
		ans+=find(q[i]-r,q[i]-l,(long long)-1e10-1e9,(long long)1e10,1);
		get(q[i],(long long)-1e10-1e9,(long long)1e10,1);
	}
	printf("%lld\n",ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38