C11SEQ - Dãy số

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;

const int N = 1e5 + 5;
int a[N], bit[3*N], n, l, r, maxID;
long long t[3*N], s[N];
map<long long, int> cmprs; //compress

void enter() {
	scanf("%d%d%d", &n, &l, &r);
	for(int i = 1; i <= n; ++i) scanf("%d", a+i);
}

void compress() {
	for(int i = 0; i <= n; ++i) {
		if(i) s[i] = s[i-1] + a[i];
		t[3*i] = s[i]; t[3*i+1] = s[i]-l+1, t[3*i+2] = s[i]-r;
	}
	sort(t, t+3*(n+1));
	const int &x = maxID = unique(t, t+3*(n+1)) - t;
	for(int i = 0; i <= n; ++i) {
		cmprs[s[i]] = x - (lower_bound(t, t+x, s[i]) - t);
		cmprs[s[i]-l+1] = x - (lower_bound(t, t+x, s[i]-l+1) - t);
		cmprs[s[i]-r] = x - (lower_bound(t, t+x, s[i]-r) - t);
	}
}

void Inc(int v) {
	for(; v <= maxID; v += v & -v) ++bit[v];
}

int sumTo(int v) {
	int res = 0;
	for(; v > 0; v -= v & -v) res += bit[v];
	return res;
}

void solve() {
	long long res = 0;
	for(int i = 0; i <= n; ++i) {
		res += sumTo(cmprs[s[i]-r]) - sumTo(cmprs[s[i]-l+1]);
		Inc(cmprs[s[i]]);
	}
	printf("%lld\n", res);
}

int main() {
	enter();
	compress();
	solve();
	return 0;
}

Download