bzoj 4627 回转寿司

Posted on | Views:

线段树.

  • 区间和可以转化为前缀和之差.记前缀和为 $sum$ ,从前往后加入数,加入到第 $i$ 个数的时候,就要算 $L\leq sum_i-sum_j\leq R,0\leq j<i$ 的 $j$ 的数目.
  • 不等式变一下,就是求 $sum_i-R\leq sum_j\leq sum_i-L$ 的数目.用权值线段树来维护,动态开点即可.

注意权值可能是负的,所以根节点的 $l,r$ 分别为 $-inf,inf$ .

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
const ll inf=1e10;
int n,L,R;
struct Segtree
{
	int idx;
	struct node
	{
		int cnt;
		int ls,rs;
		node(){cnt=ls=rs=0;}	
	}Tree[MAXN*50];
	Segtree(){idx=0;}
#define root Tree[o]
	void upd(int &o,ll l,ll r,ll pos)
	{
		if(!o)
			o=++idx;
		++root.cnt;
		if(l==r)
			return;
		ll mid=(l+r)>>1;
		if(pos<=mid)
			upd(root.ls,l,mid,pos);
		else
			upd(root.rs,mid+1,r,pos);
	}
	int query(int o,ll l,ll r,ll L,ll R)
	{
		if(L>R || R<l || l>R)
			return 0;
		if(L<=l && r<=R)
			return root.cnt;
		int res=0;
		ll mid=(l+r)>>1;
		if(L<=mid)
			res+=query(root.ls,l,mid,L,R);
		if(R>mid)
			res+=query(root.rs,mid+1,r,L,R);
		return res;
	}
}T;
int rt=0;
ll ans=0,sum=0;
int main()
{
	n=read();
	L=read(),R=read();
	T.upd(rt,-inf,inf,0);
	for(int i=1;i<=n;++i)
	{
		sum+=read();
		ans+=T.query(rt,-inf,inf,sum-R,sum-L);
		T.upd(rt,-inf,inf,sum);
	}
	cout<<ans<<endl;
	return 0;
}