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

Download