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;
}

Download