C11SEQ - Dãy số
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
long long a[N];
long long t[N];
long long L, R;
int n;
long long solve(int l, int r) {
if (l >= r) return 0;
int mid = l + r >> 1;
long long ans = solve(l, mid) + solve(mid + 1, r);
int pl = mid + 1, pr = mid + 1;
for (int i = r; i > mid; --i) {
while (pl > l && a[i] - a[pl - 1] < L) --pl;
while (pr > l && a[i] - a[pr - 1] <= R) --pr;
if (pl > pr) ans += pl - pr;
}
merge(a + l, a + mid + 1, a + mid + 1, a + r + 1, t);
for (int i = l, j = 0; i <= r; ++i, ++j) a[i] = t[j];
return ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("C11SEQ.txt", "r", stdin);
#endif // ONLINE_JUDGE
cin >> n >> L >> R;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
a[i] += a[i - 1];
}
cout << solve(0, n) << endl;
return 0;
}