bzoj4627 [BeiJing2016]回转寿司(动态开点线段树)

题目链接

大意：给你一个长度n的数组，和两个数l,r，问你有多少区间满足 $l\le {\sum }_{i=l}^r{a}_i\le r$l≤∑i=lr​ai​≤r，输出即可。
思路：枚举区间右端点j，即我们要找的就是有多少个i，使得 $i\&lt;j且l\le sum\left[j\right]-sum\left[i\right]\le r$i<j且l≤sum[j]−sum[i]≤r，那么我们建一个线段树维护前缀和出现的次数，由于空间限制，我们只能动态开点，每次开点最坏是log级别的空间消耗，

        t[++cnt]=0;
        ls[cnt]=rs[cnt]=0;
        x=cnt;

然后 剩下的就跟普通的线段树没什么区别拉

细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 1e5 + 3;
const LL mod = 1e9 + 7;
const LL inf=1e10;
int n,a[N],l,r;
LL t[N*100];
int cnt;
LL ls[N*100],rs[N*100];
LL root;
void add(LL &x,LL l,LL r,LL d){
    if(!x){
        t[++cnt]=0;
        ls[cnt]=rs[cnt]=0;
        x=cnt;
    }
    if(l==r){
        t[x]++;
        return ;
    }
    LL mid=l+r>>1;
    if(d<=mid)add(ls[x],l,mid,d);
    else add(rs[x],mid+1,r,d);
    t[x]=t[ls[x]]+t[rs[x]];
}
LL get(int now,LL l,LL r,LL x,LL y){
    if(l>=x&&r<=y){
        return t[now];
    }
    LL ans=0;
    LL mid=l+r>>1;
    if(x<=mid&&ls[now])ans+=get(ls[now],l,mid,x,y);
    if(y>mid&&rs[now])ans+=get(rs[now],mid+1,r,x,y);
    return ans;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>l>>r;
	for(int i=1;i<=n;i++)cin>>a[i];
	add(root,-inf,inf,0);
	LL ans=0,sum=0;
	for(int i=1;i<=n;i++){
	    sum+=a[i];
	    ans+=get(root,-inf,inf,sum-r,sum-l);
	    add(root,-inf,inf,sum);
	}
	cout<<ans<<endl;
	return 0;
}