https://www.lydsy.com/JudgeOnline/problem.php?id=4627
题意:求序列中和在L到R之间的字串种数。
要求的是和的范围,我们可以考虑先求一个前缀和pre,然后每个点j的贡献就是L <= pre[j] - pre[i] <= R(i < j)的i的种数了,移项一下变成
pre[j] - R <= pre[i] <= pre[j] - L
我们就可以考虑做个权值线段树维护一下所有pre,每次求贡献的时候做一个区间查询就可以了。
注意点:
1.由于范围太大又有负数,线段树要动态开点。
2.开局要加一个pre[0] = 0的前缀和
3.线段树里不必要开的点尽量不开否则可能由于空间WA
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x);
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = ,f = ;char c = getchar();while (c<'' || c>''){if (c == '-') f = -;c = getchar();}
while (c >= ''&&c <= ''){x = x * + c - '';c = getchar();}return x*f;}
const double eps = 1e-;
const int maxn = 1e5 + ;
const LL INF = 1e10 + 2e9;
const int mod = 1e9 + ;
int N,M,K;
LL L,R;
struct Tree{
LL sum;
int lt,rt;
void init(){lt = rt = sum = ;}
}tree[maxn * ];
int tot;
void check(int &t){
if(t) return;
t = ++tot;
tree[t].init();
}
void Pushup(int &t){
int ls = tree[t].lt,rs = tree[t].rt;
tree[t].sum = tree[ls].sum + tree[rs].sum;
}
void update(int &t,LL l,LL r,LL x){
check(t);
if(l == r){
tree[t].sum++;
return;
}
LL m = l + r >> ;
if(x <= m) update(tree[t].lt,l,m,x);
else update(tree[t].rt,m + ,r,x);
Pushup(t);
}
LL query(int &t,LL l,LL r,LL ql,LL qr){
if(!t) return ;
if(ql <= l && r <= qr) return tree[t].sum;
LL m = l + r >> ;
if(qr <= m) return query(tree[t].lt,l,m,ql,qr);
else if(ql > m) return query(tree[t].rt,m + ,r,ql,qr);
else return query(tree[t].lt,l,m,ql,m) + query(tree[t].rt,m + ,r,m + ,qr);
}
LL pre[maxn];
int main(){
N = read(); L = read(); R = read(); // sum[j] - L >= sum[i - 1] >= sum[j] - R;
for(int i = ; i <= N; i ++) pre[i] = read() + pre[i - ];
LL ans = ;
int root = ;
update(root,-INF,INF,);
for(int i = ; i <= N ; i ++){
if(pre[i] - R <= pre[i] - L) ans += query(root,-INF,INF,pre[i] - R,pre[i] - L);
update(root,-INF,INF,pre[i]);
}
Prl(ans);
return ;
}