C11SEQ - Dãy số
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
#define MAX 100100
using namespace std;
typedef long long ll;
ll a[MAX];
ll s[MAX];
ll v[3*MAX];
ll l,r;
ll t[3*MAX];
int n;
int cs[MAX];
int cl[MAX];
int cr[MAX];
void init(void) {
scanf("%d",&n);
scanf("%lld",&l);
scanf("%lld",&r);
int i;
s[0]=0;
for (i=1;i<=n;i=i+1) {
scanf("%lld",&a[i]);
s[i]=s[i-1]+a[i];
}
for (i=0;i<=3*n+10;i=i+1) t[i]=0;
}
void compress(void) {
int i;
for (i=0;i<=n;i=i+1) {
v[3*i+1]=s[i];
v[3*i+2]=s[i]+l;
v[3*i+3]=s[i]+r;
}
sort(&v[1],&v[3*n+4]);
for (i=0;i<=n;i=i+1) {
cs[i]=lower_bound(&v[1],&v[3*n+4],s[i])-&v[0]+1;
cl[i]=lower_bound(&v[1],&v[3*n+4],s[i]+l)-&v[0]+1;
cr[i]=lower_bound(&v[1],&v[3*n+4],s[i]+r)-&v[0]+1;
}
}
void update(int x) {
while (1<=x && x<=3*n+10) {
t[x]++;
x=x+(x&(-x));
}
}
ll get(int x) {
ll res=0;
while (1<=x && x<=3*n+10) {
res=res+t[x];
x=x&(x-1);
}
return (res);
}
ll sum(int a,int b) {
return (get(b)-get(a-1));
}
void process(void) {
int i;
ll res=0;
for (i=n;i>=0;i=i-1) {
res=res+sum(cl[i],cr[i]);
update(cs[i]);
}
printf("%lld\n",res);
}
int main(void) {
init();
compress();
process();
return 0;
}