RETURN

题目连接：Large Sum Subarray

Large Sum Subarray

本题寻找以下配对的个数：$(i,j),i\leq j,\sum_{k=i}^ja_k>t$。通过求前缀和，我们可以把区间转换为两点的比较：$(i+1,j), S_j-S_{i}>t$。

联想一道经典的求逆序对的问题，题目求以下配对的个数：$(i,j),i\leq j, a_j>a_i$。本题稍加改变，也可以变为 $(i,j),i\leq j, a_j<a_i+t$。

归并排序的过程中（升序），在 merge 时，如果 $a_i+t$（第一部分） 比 $a_j$（第二部分） 小，那么 $a_i+t$ 比 $a_k,k>j$ 都要小。故我们把第一部分指针后移，并加上 $i$ 可以配对的数量 $R-j+1$，$R$ 是第二部分的右边界。

解决问后可以再想想，如果排序是降序的，求顺序对和求逆序对的代码又应该放在哪里？该如何证明正确性？

额外的注意事项

使用 C++ 的同学，读入时若使用 cin 需要加速，或使用 scanf 读入

参考代码

#include <bits/stdc++.h>
using namespace std;

#define n_max 1000000

int64_t t, ans;
int64_t a[n_max + 1], s[n_max + 1], tmp[n_max + 1];

void merge(int64_t* a, int left, int mid, int right) {
    int i, j, k;
    // count
    i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (a[i] + t < a[j]) {
            i++;
            // ordered pair counted here
            ans += right - j + 1;
        } else {
            j++;
            // inversion pair counted here
        }
    }

    // merge
    i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) {
            tmp[k++] = a[i++];
        } else {
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= right) tmp[k++] = a[j++];
    for (int i = left; i <= right; ++i) a[i] = tmp[i];
}

void mergesort(int64_t* a, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid + 1, right);
    merge(a, left, mid, right);
}

int main() {
    // Read
    int n;
    scanf("%d%lld", &n, &t);
    /*
        Calculate s[i] to be the presum of a, then sum(a[i..j])=s[j] - s[i-1]
        Problem (rephrase): find i<j, s[j] - s[i-1] > t
    */
    s[0] = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", a + i);
        s[i + 1] = a[i] + s[i];
    }

    // Solve
    /*
        Inspired by calculating inversion in array by mergesort (i<j, a[j]>a[i])
    */
    mergesort(s, 0, n);

    // Write
    printf("%lld\n", ans);

    return 0;
}