记录编号	572253	评测结果	AAAAAAAAAA
题目名称	[BJOI2016]回转寿司	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.435 s
提交时间	2022-06-29 16:23:55	内存使用	10.42 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=100000+5;
typedef long long ll;
int n,np=0;
ll p[4*N],q[4*N];
ll a[N]={0},l,r;
ll ans=0;
ll qzh[N]={0};
int len[4*N];
int lowbit(int x){
    return x&(-x);
}
void add(int x,int y){
    if (x==0)return ;
    for (int i=x;i<=np;i+=lowbit(i)){
        len[i]+=y;
    }
    return ;
}
int getsum(int x){
    int t=0;
    for (int i=x;i>0;i-=lowbit(i)){
        t+=len[i];
    }
    return t;
}
int main(){
    freopen ("bjoi2016_hzss.in","r",stdin);
    freopen ("bjoi2016_hzss.out","w",stdout);
    scanf("%d%lld%lld",&n,&l,&r);
    p[++np]=qzh[0]=0;
    for (int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        qzh[i]=qzh[i-1]+a[i];
        p[++np]=qzh[i];p[++np]=qzh[i]-l;p[++np]=qzh[i]-r;
    }
    
    for (int i=1;i<=np;i++)q[i]=p[i];
    sort(q+1,q+np+1);
    np=unique(q+1,q+np+1)-q-1;
    for (int i=1;i<=3*n+1;i++){
        p[i]=lower_bound(q+1,q+np+1,p[i])-q;
    }
    add(p[1],1);
    for (int i=1;i<=n;i++){
        ans+=getsum(p[3*i])-getsum(p[3*i+1]-1);
        add(p[3*i-1],1);
    }
    printf("%lld\n",ans);
    return 0;
}