bzoj4627

前言：要不是bzoj刚好在我做完这题时又挂了，我才懒得写呢

这题感觉不难吧。。

首先我们知道任何一个子串两个后缀的差值，于是我们先把全部后缀弄出来

然后排个序

很容易吧问题转换为<=r的减去<l的有多少个

我们暴力枚举左端点，接着对于当前的这个后缀，我们看看比他后的有多少的后缀满足条件

至于怎么判断，我们可以算出后面的后缀值的大小，接着在一开始弄出来里面的二分就好了

我们每处理完一位就往右挪一位，怎么删除呢，我们开个树状数组就好了嘛，来维护这个后缀之前有多少个数，具体看代码

总的之间复杂度是nlogn的

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=100005;
LL n;
LL a[N];
LL sum=0;
struct qq 
{LL x,id;
}lalal[N];
LL ans=0;
LL f[N];
LL lb (LL x)
{return x&(-x);
}
void change (LL x,LL y)
{while (x<=n){f[x]+=y;x+=lb(x);}
}
LL get (LL x)
{LL tot=0;while (x>=1){tot=tot+f[x];x-=lb(x);}return tot;
}
LL find (LL x)//多少个数比这个大 
{LL l=1,r=n;LL ok=-1;while (l<=r){LL mid=(l+r)>>1;if (lalal[mid].x>=x){ok=mid;r=mid-1;}else l=mid+1;}if (ok==-1) return 0;return get(n)-get(ok-1);
}
LL pos[N];
bool cmp (qq a,qq b){return a.x<b.x;}
int main()
{LL l,r;scanf("%lld%lld%lld",&n,&l,&r);if (l>r) {printf("0\n");return 0;}for (LL u=1;u<=n;u++) {scanf("%lld",&a[u]);sum=sum+a[u];}
//  printf("%lld\n",sum);//n++;a[n]=0;memset(f,0,sizeof(f));for (LL u=n;u>=1;u--) lalal[u].x=lalal[u+1].x+a[u],lalal[u].id=u;sort(lalal+1,lalal+1+n,cmp);for (LL u=1;u<=n;u++) pos[lalal[u].id]=u;for (LL u=1;u<=n;u++) change(u,1);for (LL u=1;u<=n;u++){   change(pos[u],-1);ans=ans+find(sum-r)-find(sum-l+1);if (sum>=l&&sum<=r) ans++;//printf("%lld %lld %lld %lld %lld %lld\n",u,ans,sum-r,find(sum-r),sum-l+1,find(sum-l+1));//printf("%lld %lld %lld %lld %lld\n",sum,sum-r,find(sum-r),sum-l+1,find(sum-l+1));sum=sum-a[u];}printf("%lld\n",ans);return 0;
}