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