小店的经营分析

题目分析

给定 $n$ 天的经营数据（盈利为正，亏损为负），以及一个目标利润区间 $[\text{lower}, \text{upper}]$ ，求有多少个连续经营周期（子数组）的总利润恰好落在目标区间内。

即统计满足 $\text{lower} \le \sum_{k=i}^{j} \text{profit}[k] \le \text{upper}$ 的 $(i, j)$ 对数。

思路

归并排序 + 前缀和

子数组和可以用前缀和表示： $\text{sum}(i, j) = \text{prefix}[j+1] - \text{prefix}[i]$ 。问题转化为：在前缀和数组 $\text{prefix}[0..n]$ 中，统计满足 $\text{lower} \le \text{prefix}[j] - \text{prefix}[i] \le \text{upper}$ （且 $j > i$ ）的有序对 $(i, j)$ 的个数。

暴力枚举所有对是 $O(n^2)$ 的，对于 $n \le 10^5$ 会超时。我们利用归并排序在合并过程中高效统计。

关键观察：在归并排序的合并阶段，左半部分和右半部分各自已排好序。对于左半部分的每个 $\text{prefix}[i]$ ，我们要在右半部分找满足 $\text{lower} \le \text{prefix}[j] - \text{prefix}[i] \le \text{upper}$ 的 $j$ ，即 $\text{prefix}[i] + \text{lower} \le \text{prefix}[j] \le \text{prefix}[i] + \text{upper}$ 。

由于右半部分已排序，可以用双指针 $j_1, j_2$ 维护满足条件的区间 $[j_1, j_2)$ 。随着 $i$ 从左到右遍历（左半部分也已排序， $\text{prefix}[i]$ 递增）， $j_1$ 和 $j_2$ 也单调递增，因此统计部分的总复杂度为 $O(n)$ 。

以样例 2 验证： $\text{profit} = [-3, 4, -2]$ ， $\text{prefix} = [0, -3, 1, -1]$ ， $[\text{lower}, \text{upper}] = [-3, 2]$ 。

所有子数组和： $-3, 1, -1, 4, 2, -2$ 。落在 $[-3, 2]$ 内的有： $-3, 1, -1, 2, -2$ ，共 $5$ 个，与预期一致。

复杂度

时间复杂度： $O(n \log n)$ ，归并排序每层合并 $O(n)$ ，共 $O(\log n)$ 层
空间复杂度： $O(n)$ ，归并排序的辅助数组

代码

C++
Java
Python3
JavaScript

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

int countRangeSum(vector<long long>& prefix, int lo, int hi, long long lower, long long upper) {
    if (lo >= hi) return 0;
    int mid = lo + (hi - lo) / 2;
    int count = countRangeSum(prefix, lo, mid, lower, upper)
              + countRangeSum(prefix, mid + 1, hi, lower, upper);
    // 对于左半部分的每个 prefix[i]，统计右半部分中满足条件的 j
    int j1 = mid + 1, j2 = mid + 1;
    for (int i = lo; i <= mid; i++) {
        while (j1 <= hi && prefix[j1] - prefix[i] < lower) j1++;
        while (j2 <= hi && prefix[j2] - prefix[i] <= upper) j2++;
        count += j2 - j1;
    }
    // 归并排序
    vector<long long> tmp(hi - lo + 1);
    int p = lo, q = mid + 1, idx = 0;
    while (p <= mid && q <= hi) {
        if (prefix[p] <= prefix[q]) tmp[idx++] = prefix[p++];
        else tmp[idx++] = prefix[q++];
    }
    while (p <= mid) tmp[idx++] = prefix[p++];
    while (q <= hi) tmp[idx++] = prefix[q++];
    for (int i = 0; i < idx; i++) prefix[lo + i] = tmp[i];
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> prefix(n + 1);
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        scanf("%lld", &x);
        prefix[i] = prefix[i - 1] + x;
    }
    long long lower, upper;
    scanf("%lld %lld", &lower, &upper);
    printf("%d\n", countRangeSum(prefix, 0, n, lower, upper));
    return 0;
}

import java.util.*;

public class Main {
    static long lower, upper;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] prefix = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + sc.nextLong();
        }
        lower = sc.nextLong();
        upper = sc.nextLong();
        System.out.println(mergeCount(prefix, 0, n));
    }

    static int mergeCount(long[] arr, int lo, int hi) {
        if (lo >= hi) return 0;
        int mid = lo + (hi - lo) / 2;
        int count = mergeCount(arr, lo, mid) + mergeCount(arr, mid + 1, hi);
        int j1 = mid + 1, j2 = mid + 1;
        for (int i = lo; i <= mid; i++) {
            while (j1 <= hi && arr[j1] - arr[i] < lower) j1++;
            while (j2 <= hi && arr[j2] - arr[i] <= upper) j2++;
            count += j2 - j1;
        }
        long[] tmp = new long[hi - lo + 1];
        int p = lo, q = mid + 1, idx = 0;
        while (p <= mid && q <= hi) {
            if (arr[p] <= arr[q]) tmp[idx++] = arr[p++];
            else tmp[idx++] = arr[q++];
        }
        while (p <= mid) tmp[idx++] = arr[p++];
        while (q <= hi) tmp[idx++] = arr[q++];
        System.arraycopy(tmp, 0, arr, lo, idx);
        return count;
    }
}

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + int(input_data[idx]); idx += 1
    lower = int(input_data[idx]); idx += 1
    upper = int(input_data[idx]); idx += 1

    # 迭代归并排序（自底向上），避免递归栈溢出
    ans = 0
    size = 1
    while size <= n:
        lo = 0
        while lo <= n:
            mid = min(lo + size - 1, n)
            hi = min(lo + 2 * size - 1, n)
            if mid >= hi:
                lo += 2 * size
                continue
            # 统计跨越左右两半的满足条件的对
            j1 = mid + 1
            j2 = mid + 1
            for i in range(lo, mid + 1):
                while j1 <= hi and prefix[j1] - prefix[i] < lower:
                    j1 += 1
                while j2 <= hi and prefix[j2] - prefix[i] <= upper:
                    j2 += 1
                ans += j2 - j1
            # 归并
            tmp = []
            p, q = lo, mid + 1
            while p <= mid and q <= hi:
                if prefix[p] <= prefix[q]:
                    tmp.append(prefix[p]); p += 1
                else:
                    tmp.append(prefix[q]); q += 1
            while p <= mid:
                tmp.append(prefix[p]); p += 1
            while q <= hi:
                tmp.append(prefix[q]); q += 1
            prefix[lo:lo + len(tmp)] = tmp
            lo += 2 * size
        size *= 2
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const vals = lines[1].split(' ').map(Number);
    const [lower, upper] = lines[2].split(' ').map(Number);
    const prefix = new Array(n + 1);
    prefix[0] = 0;
    for (let i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + vals[i - 1];
    }
    console.log(mergeCount(prefix, 0, n, lower, upper));
});

function mergeCount(arr, lo, hi, lower, upper) {
    if (lo >= hi) return 0;
    const mid = lo + ((hi - lo) >> 1);
    let count = mergeCount(arr, lo, mid, lower, upper)
              + mergeCount(arr, mid + 1, hi, lower, upper);
    let j1 = mid + 1, j2 = mid + 1;
    for (let i = lo; i <= mid; i++) {
        while (j1 <= hi && arr[j1] - arr[i] < lower) j1++;
        while (j2 <= hi && arr[j2] - arr[i] <= upper) j2++;
        count += j2 - j1;
    }
    const tmp = [];
    let p = lo, q = mid + 1;
    while (p <= mid && q <= hi) {
        if (arr[p] <= arr[q]) tmp.push(arr[p++]);
        else tmp.push(arr[q++]);
    }
    while (p <= mid) tmp.push(arr[p++]);
    while (q <= hi) tmp.push(arr[q++]);
    for (let i = 0; i < tmp.length; i++) arr[lo + i] = tmp[i];
    return count;
}