Sum.cpp

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <cctype>
#include <cstdio>

using namespace std;

typedef long long int64;
typedef unsigned uint;

#define  mp make_pair
int64 n, k;

int64 merge(vector <int64> &v, int l, int r) {
    int m = (l + r) / 2;
    vector <pair<int64, bool>> a;
    int i = l, j = m + 1;
    int64 sum = 0;
    int64 s = 0;
    int k1 = 0;
    while (i <= m || j <= r) {
        if (i > m) {
            while (k1 < (int) a.size() && v[j] - a[k1].first >= k) {
                if (!a[k1].second) s++;
                k1++;
            }
            sum += s;
            a.push_back(mp(v[j], 1));
            j++;
            continue;
        }
        if (j > r) {
            // sum += find(a, v[i]-k);
            a.push_back(mp(v[i], 0));
            i++;
            continue;
        }
        if (v[i] <= v[j]) {
            // sum += find(a,v[i]-k);
            a.push_back(mp(v[i], 0));
            i++;
        } else {
            while (k1 < (int) a.size() && v[j] - a[k1].first >= k) {
                if (!a[k1].second) s++;
                k1++;
            }
            sum += s;
            a.push_back(mp(v[j], 1));
            j++;
        }
    }
    for (int i = l; i <= r; ++i) {
        v[i] = a[i - l].first;
    }

    return sum;
}

int64 MergeSort(vector <int64> &v, int l, int r) {
    if (l >= r) return 0;
    int m = (l + r) / 2;
    int64 sum = MergeSort(v, l, m);
    sum += MergeSort(v, m + 1, r);
    sum += merge(v, l, r);
    return sum;
}

unsigned int cur = 0;
unsigned int a, b;

unsigned int next24() {
    cur = cur * a + b;
    return cur >> 8;
}

unsigned int next() {
    unsigned int a = next24(), b = next24();
    return (a << 8) ^ b;
}


int main() {
    // freopen("read.txt", "r", stdin);
    freopen("bigseg.in", "r", stdin);
    freopen("bigseg.out", "w", stdout);
    cin >> n >> k;
    cin >> a >> b;
    vector <int64> v(n);
    for (int i = 0; i < n; ++i) {
        v[i] = (int64)((int)next());
        // cin >> v[i];
    }
    vector <int64> p;
    p.push_back(0);
    for (int i = 0; i < n; ++i) {
        p.push_back(p.back() + v[i]);
    }
    cout << MergeSort(p, 0, (int)p.size() - 1) << endl;;
    return 0;
}