解题思路

把原数组转为前缀和：pre[0]=0，pre[i]=papers[0..i-1]之和。任意连续子段 [l..r] 的和为： sum = pre[r+1] - pre[l]。

要求 left <= sum <= right，等价于对每个 j = r+1，统计之前的 i < j 中有多少个 pre[i] 落在区间： pre[i] ∈ [ pre[j]-right , pre[j]-left ]。

所以问题变成：按顺序枚举 pre[j]，动态维护已出现的前缀和值集合，支持“统计某个数值区间内的出现次数”。 做法：对所有 pre 做坐标压缩，用树状数组维护出现次数；区间计数用二分把值域区间映射成下标区间，再用树状数组前缀和相减得到答案。

复杂度分析

• 时间复杂度：O(n log n)（排序压缩 O(n log n)，每个前缀两次二分+两次树状数组 O(log n)）
• 空间复杂度：O(n)（前缀和、压缩数组、树状数组）

代码实现

Python

import sys
from bisect import bisect_left, bisect_right

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, v):
        # 树状数组单点加
        while i <= self.n:
            self.bit[i] += v
            i += i & -i

    def sum(self, i):
        # 前缀和 [1..i]
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

def count_subarrays_in_range(arr, left, right):
    n = len(arr)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + arr[i]

    # 坐标压缩：只需要压缩所有前缀和本身
    vals = sorted(set(pre))
    bit = BIT(len(vals))

    ans = 0
    # 先加入 pre[0]=0
    bit.add(bisect_left(vals, 0) + 1, 1)

    for j in range(1, n + 1):
        pj = pre[j]
        # 需要统计 pre[i] ∈ [pj-right, pj-left]
        lo = pj - right
        hi = pj - left

        # idx_hi = <=hi 的个数（0..m），idx_lo = <lo 的个数（0..m）
        idx_hi = bisect_right(vals, hi)
        idx_lo = bisect_left(vals, lo)

        # 区间计数 = 前缀计数差
        ans += bit.sum(idx_hi) - bit.sum(idx_lo)

        # 加入当前前缀和
        bit.add(bisect_left(vals, pj) + 1, 1)

    return ans

def main():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    arr = list(map(int, data[1:1 + n]))
    left = int(data[1 + n])
    right = int(data[2 + n])
    print(count_subarrays_in_range(arr, left, right))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {

    // 树状数组（Fenwick）
    static class BIT {
        int n;
        long[] bit;
        BIT(int n) {
            this.n = n;
            this.bit = new long[n + 1];
        }
        void add(int i, long v) {
            // 单点加
            while (i <= n) {
                bit[i] += v;
                i += i & -i;
            }
        }
        long sum(int i) {
            // 前缀和 [1..i]
            long s = 0;
            while (i > 0) {
                s += bit[i];
                i -= i & -i;
            }
            return s;
        }
    }

    // lowerBound：第一个 >= x 的位置（0..len）
    static int lowerBound(long[] a, long x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] >= x) r = m;
            else l = m + 1;
        }
        return l;
    }

    // upperBound：第一个 > x 的位置（0..len）
    static int upperBound(long[] a, long x) {
        int l = 0, r = a.length;
        while (l < r) {
            int m = (l + r) >>> 1;
            if (a[m] > x) r = m;
            else l = m + 1;
        }
        return l;
    }

    static long countSubarraysInRange(int[] arr, long left, long right) {
        int n = arr.length;
        long[] pre = new long[n + 1];
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + arr[i];
        }

        // 坐标压缩：排序去重所有前缀和
        long[] tmp = Arrays.copyOf(pre, pre.length);
        Arrays.sort(tmp);
        int m = 0;
        for (int i = 0; i < tmp.length; i++) {
            if (i == 0 || tmp[i] != tmp[i - 1]) tmp[m++] = tmp[i];
        }
        long[] vals = Arrays.copyOf(tmp, m);

        BIT bit = new BIT(m);
        long ans = 0;

        // 加入 pre[0]=0
        int pos0 = lowerBound(vals, 0) + 1;
        bit.add(pos0, 1);

        for (int j = 1; j <= n; j++) {
            long pj = pre[j];
            long lo = pj - right;
            long hi = pj - left;

            // idxHi：<=hi 的个数；idxLo：<lo 的个数
            int idxHi = upperBound(vals, hi);
            int idxLo = lowerBound(vals, lo);

            // 区间计数 = 前缀计数差
            ans += bit.sum(idxHi) - bit.sum(idxLo);

            // 加入当前前缀和
            int pos = lowerBound(vals, pj) + 1;
            bit.add(pos, 1);
        }

        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 默认输入合法，使用 BufferedReader 简洁读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String line;
        while ((line = br.readLine()) != null) sb.append(line).append(' ');
        String[] parts = sb.toString().trim().split("\\s+");

        int idx = 0;
        int n = Integer.parseInt(parts[idx++]);
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(parts[idx++]);
        long left = Long.parseLong(parts[idx++]);
        long right = Long.parseLong(parts[idx++]);

        System.out.println(countSubarraysInRange(arr, left, right));
    }
}

C++

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

// 树状数组（Fenwick）
struct BIT {
    int n;
    vector<long long> bit;
    BIT(int n): n(n), bit(n + 1, 0) {}

    void add(int i, long long v) {
        // 单点加
        for (; i <= n; i += i & -i) bit[i] += v;
    }

    long long sum(int i) {
        // 前缀和 [1..i]
        long long s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

long long count_subarrays_in_range(const vector<int>& a, long long left, long long right) {
    int n = (int)a.size();
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];

    // 坐标压缩：所有前缀和排序去重
    vector<long long> vals = pre;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    BIT bit((int)vals.size());
    long long ans = 0;

    // 加入 pre[0]=0
    int pos0 = (int)(lower_bound(vals.begin(), vals.end(), 0LL) - vals.begin()) + 1;
    bit.add(pos0, 1);

    for (int j = 1; j <= n; j++) {
        long long pj = pre[j];
        long long lo = pj - right;
        long long hi = pj - left;

        // idxHi：<=hi 的个数；idxLo：<lo 的个数（都是 0..m）
        int idxHi = (int)(upper_bound(vals.begin(), vals.end(), hi) - vals.begin());
        int idxLo = (int)(lower_bound(vals.begin(), vals.end(), lo) - vals.begin());

        // 区间计数 = 前缀计数差
        ans += bit.sum(idxHi) - bit.sum(idxLo);

        // 加入当前前缀和
        int pos = (int)(lower_bound(vals.begin(), vals.end(), pj) - vals.begin()) + 1;
        bit.add(pos, 1);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    long long left, right;
    cin >> left >> right;

    cout << count_subarrays_in_range(a, left, right) << "\n";
    return 0;
}

题目描述

今天，小明的数学老师带来了一叠数字卡牌，每张卡牌上标有数字，有正有负也有零。老师打乱了卡牌顺序，并将牌面展示出来。接着老师在黑板上写下了一个闭区间范围 [left, right]。

老师对小明说：“你可以从这叠卡牌中任意抽取一叠，起始位置不限，抽取的张数不限，但是有个要求，你抽取出的卡牌，牌面加起来的和需要落在黑板上的区间范围内。小明，你算算看，一共能有几种抽取方法？”

小明听完，眼冒金星。你能帮助小明写个程序，算出有几种方法吗？

输入描述

• 第一行：纸牌数量 n（1 < n <= 10000）
• 第二行：纸牌数组 papers[]（-255 <= papers[i] <= 255），共 n 个整数
• 第三行：目标闭区间的左值 left 与右值 right（-2550000 <= left <= right <= 2550000）

输出描述

• 一个整数，表示满足条件的抽取方法种类数。

样例1

输入：

4
1 -1 1 -1
0 0

输出：

4

解释：
共有4张纸牌，牌面数字为1，-1，1，-1，方法为取第1张到2张，取第2张到第3张，取第3张到4张，取第1到4张，共4种

样例2

输入：

3
-3 4 -2
-3 2

输出：

5