题解 | #小店的经营分析#

题目链接

小店的经营分析

题目描述

小张记录了连续 $N$ 天的经营数据 $P_i$ （盈利为正，亏损为负）。给定目标利润区间 $[L, R]$ ，请统计有多少个连续经营周期（即连续子数组）的总利润恰好落在该区间内。

输入：

第一行：一个整数 $N$ ，代表记录的总天数。( $1 < N \le 10000$ )
第二行： $N$ 个整数，代表数组 $P$ ，其中 $P_i$ 表示第 $i$ 天的利润。( $-255 \le P_i \le 255$ )
第三行：两个整数 $L$ 和 $R$ ，用空格隔开，代表目标利润区间的左右边界。( $-2550000 \le L \le R \le 2550000$ )

输出：

一个整数，表示总利润在区间 $[L, R]$ 内的连续经营周期的总数量。

解题思路

本题的核心是统计和在 $[L, R]$ 范围内的子数组数量。

前缀和：定义前缀和 $S_i = \sum_{j=1}^{i} P_j$ ，并令 $S_0 = 0$ 。任一连续经营周期 $[i, j]$ （ $1 \le i \le j \le N$ ）的总利润可以表示为 $S_j - S_{i-1}$ 。我们需要统计满足 $L \le S_j - S_{i-1} \le R$ 的索引对 $(i-1, j)$ 。
算法选择：
- 暴力枚举 ( $O(N^2)$ )：枚举所有子数组起点和终点。对于 $N = 10000$ ，子数组数量级为 $\frac{N(N+1)}{2} \approx 5 \cdot 10^7$ 。在 C++ 和 Java 中，这种复杂度通常可以在 1 秒内通过；但在 Python 中会超时。
- 前缀和 + 树状数组 ( $O(N \log N)$ )：将不等式变形为 $S_j - R \le S_{i-1} \le S_j - L$ 。在遍历 $j$ 的过程中，利用树状数组统计满足条件的 $S_{i-1}$ 。这种方法对 $N=10000$ 非常轻松，且适用于更大的 $N$ 。
优化与细节：
- 考虑到 $N=10000$ 的数据范围，C++ 使用 $O(N^2)$ 更加简洁。
- Python 必须使用优化算法（如树状数组或归并排序思想）才能通过。为了保证通用性和专业性，本题解采用 $O(N \log N)$ 的树状数组方案。
- 由于前缀和的值域范围在 $[-2.55 \cdot 10^6, 2.55 \cdot 10^6]$ ，我们需要对前缀和进行离散化处理。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

struct FenwickTree {
    int n;
    vector<int> tree;
    FenwickTree(int size) : n(size), tree(size + 1, 0) {}
    void update(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    int query(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) res += tree[i];
        return res;
    }
    int query(int l, int r) {
        return l > r ? 0 : query(r) - query(l - 1);
    }
};

int main() {
    int n;
    cin >> n;
    vector<LL> s(n + 1, 0);
    vector<LL> all_sums;
    all_sums.push_back(0);
    for (int i = 1; i <= n; ++i) {
        LL p;
        cin >> p;
        s[i] = s[i - 1] + p;
        all_sums.push_back(s[i]);
    }
    LL L, R;
    cin >> L >> R;

    sort(all_sums.begin(), all_sums.end());
    all_sums.erase(unique(all_sums.begin(), all_sums.end()), all_sums.end());

    auto getIdx = [&](LL val) {
        return lower_bound(all_sums.begin(), all_sums.end(), val) - all_sums.begin() + 1;
    };

    FenwickTree ft(all_sums.size());
    LL ans = 0;

    for (int j = 0; j <= n; ++j) {
        LL val_low = s[j] - R;
        LL val_high = s[j] - L;
        
        int idx_l = lower_bound(all_sums.begin(), all_sums.end(), val_low) - all_sums.begin() + 1;
        int idx_r = upper_bound(all_sums.begin(), all_sums.end(), val_high) - all_sums.begin();
        
        ans += ft.query(idx_l, idx_r);
        ft.update(getIdx(s[j]), 1);
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class FenwickTree {
        int n;
        int[] tree;
        FenwickTree(int size) {
            this.n = size;
            this.tree = new int[size + 1];
        }
        void update(int i, int delta) {
            for (; i <= n; i += i & -i) tree[i] += delta;
        }
        int query(int i) {
            int res = 0;
            for (; i > 0; i -= i & -i) res += tree[i];
            return res;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] s = new long[n + 1];
        List<Long> allSums = new ArrayList<>();
        allSums.add(0L);
        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + sc.nextLong();
            allSums.add(s[i]);
        }
        long L = sc.nextLong();
        long R = sc.nextLong();

        Collections.sort(allSums);
        List<Long> uniqueSums = new ArrayList<>();
        if (!allSums.isEmpty()) {
            uniqueSums.add(allSums.get(0));
            for (int i = 1; i < allSums.size(); i++) {
                if (!allSums.get(i).equals(allSums.get(i - 1))) {
                    uniqueSums.add(allSums.get(i));
                }
            }
        }

        FenwickTree ft = new FenwickTree(uniqueSums.size());
        long ans = 0;
        for (int j = 0; j <= n; j++) {
            long valLow = s[j] - R;
            long valHigh = s[j] - L;

            int idxL = Collections.binarySearch(uniqueSums, valLow);
            if (idxL < 0) idxL = -(idxL + 1);
            
            int idxR = Collections.binarySearch(uniqueSums, valHigh);
            if (idxR < 0) idxR = -(idxR + 1) - 1;

            ans += ft.query(idxR + 1) - ft.query(idxL);
            
            int curIdx = Collections.binarySearch(uniqueSums, s[j]);
            ft.update(curIdx + 1, 1);
        }
        System.out.println(ans);
    }
}

import bisect

def solve():
    n = int(input())
    p_list = list(map(int, input().split()))
    l_bound, r_bound = map(int, input().split())

    s = [0] * (n + 1)
    for i in range(n):
        s[i + 1] = s[i] + p_list[i]
    
    # 离散化
    all_sums = sorted(list(set(s)))
    tree_size = len(all_sums)
    bit = [0] * (tree_size + 1)
    
    def update(i, delta):
        while i <= tree_size:
            bit[i] += delta
            i += i & (-i)
            
    def query(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & (-i)
        return res

    ans = 0
    for val_s in s:
        val_low = val_s - r_bound
        val_high = val_s - l_bound
        
        idx_l = bisect.bisect_left(all_sums, val_low) + 1
        idx_r = bisect.bisect_right(all_sums, val_high)
        
        ans += query(idx_r) - query(idx_l - 1)
        
        cur_idx = bisect.bisect_left(all_sums, val_s) + 1
        update(cur_idx, 1)
        
    print(ans)

if __name__ == "__main__":
    solve()

算法及复杂度

算法：前缀和 + 离散化 + 树状数组。
时间复杂度： $\mathcal{O}(N \log N)$ 。计算前缀和为 $\mathcal{O}(N)$ ，排序离散化为 $\mathcal{O}(N \log N)$ ，树状数组操作为 $\mathcal{O}(N \log N)$ 。针对 $N=10000$ 的规模，该算法非常高效。
空间复杂度： $\mathcal{O}(N)$ 。用于存储前缀和、离散化数组及树状数组。