题目描述：
给出一个长度为 $n$ 的整数数组nums，以及两个整数 $lower$ 和 $upper$ 。求数组中，区间和值位于 $[lower, upper]$ 中的区间段个数。
数据范围：
$1\le n \le 10^5;-2^{31}\le nums[i]\le2^{31}-1;-10^5\le lower\le upper\le 10^5$
题解：
树状数组：
容易想到使用树状数组维护前缀和 $[0,max\_sum]$ 出现的次数，然后对次数求区间和可以得到答案。
对于每个 $sum[i]$ 需要找出 $sum[i] \pm lower,sum[i]\pm upper$ 。但是由于遍历到 $sum[i]+upper$ 或 $sum[i]+lower$ 会出现重复，因此只需要找 $sum[i] -lower$ 和 $sum[i]-upper$ 即可。两者之间的 $ sum[i] - upper\le sum[j] \le sum[i] - lower$ 。因此满足 $lower \le sum[i] - sum[j] \le upper$ 。答案就是 $query(sum[i] - lower) - query(sum[i]-upper-1)$ 。
因为数比较大，所以进行离散化处理，将 $sum[i] - lower,sum[i] - upper$ 以及 $sum[i]$ 一起离散化。
同时注意需要把0也离散化，因为前缀和是 $[0,max\_sum]$ ，如果 $sum[0] = lower$ ，不放入 $0$ 的话，这个就统计不到。不放入 $0$ 的话需要提前把 $0$ 放到前缀和里面。此外需要注意把离散化到 $[1,max\_size]$ 。可以参考3662.最大上升子序列和 | Luobuyu’s Blog。最后更新 $sum[i]$ 出现的次数。
归并排序：
考虑归并排序做法，对前缀和数组 $sum$ 进行归并排序操作。
对两个升序子数组 $n_1,n_2$ 合并时，需要找出所有的 $n_2[j] - n_1[i]\in[lower,upper]$ 。可以使用双指针操作 $l,r$ 首先指向 $n_2[0]$ ，对于 $n_1[0]$ 首先移动 $l$ 指针，直到 $n_2[l]\ge n_1[0] + lower$ ；然后移动 $r$ ，直到 $n_2[r] \gt n_1[0]$ ，对解的贡献就为 $r - l$ 。
然后考虑 $n_1[1]$ ，因为 $n_1[1] \gt n_1[0]$ ，因此 $n_1[1]$ 的 $l,r$ 一定是在 $n_1[0]$ 的 $l,r$ 后面，只需要在当前位置接着移动 $l,r$ 即可。复杂度是 $O(n)$ 的，由于二分是 $O(\log(n))$ ，因此总体复杂度是 $O(n\log(n))$ 。
代码：
树状数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
struct Tree
{
vector<int> c;
int max_size;
Tree(int n) : c(n + 1), max_size(n) {}
int lowbit(int x) { return x & -x; }
void add(int index, int value)
{
while (index <= max_size)
{
c[index] += value;
index += lowbit(index);
}
}
int query(int index)
{
int ans = 0;
while (index >= 1)
{
ans += c[index];
index -= lowbit(index);
}
return ans;
}
};
int countRangeSum(vector<int> &nums, int lower, int upper)
{
int n = nums.size();
vector<long long> sum(n, 0);
long long tmp = 0;
for (int i = 0; i < n; ++i)
{
tmp += nums[i];
sum[i] = tmp;
}
vector<long long> b;
b.reserve(n);
for (int i = 0; i < n; ++i)
{
b.emplace_back(sum[i]);
b.emplace_back(sum[i] - lower);
b.emplace_back(sum[i] - upper);
}
b.emplace_back(-pow(2, 31) * 1e5 - 1);
b.emplace_back(0);
sort(b.begin(), b.end());
int max_size = unique(b.begin(), b.end()) - b.begin();
int ans = 0;
Tree tree(max_size);
int zero = lower_bound(b.begin(), b.begin() + max_size, 0) - b.begin();
tree.add(zero, 1);
for (int i = 0; i < n; ++i)
{
int sum_i = lower_bound(b.begin(), b.begin() + max_size, sum[i]) - b.begin();
int sum_lower = lower_bound(b.begin(), b.begin() + max_size, sum[i] - lower) - b.begin();
int sum_upper = lower_bound(b.begin(), b.begin() + max_size, sum[i] - upper) - b.begin();
ans += tree.query(sum_lower) - tree.query(sum_upper - 1);
tree.add(sum_i, 1);
}
return ans;
}
};
|
归并排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
int ans = 0, lower, upper;
vector<long long> tmp;
void merge_sort(vector<long long> &nums, int l, int r)
{
if (l >= r)
return;
int mid = l + ((r - l) >> 1);
merge_sort(nums, l, mid);
merge_sort(nums, mid + 1, r);
mix(nums, l, mid, r);
}
void mix(vector<long long> &nums, int l, int mid, int r)
{
int i = l, j = mid + 1, k = l;
int l0 = i, l1 = j, l2 = j;
while (l0 <= mid)
{
while (l1 <= r && nums[l1] < nums[l0] + lower)
l1++;
while (l2 <= r && nums[l2] <= nums[l0] + upper)
l2++;
ans += l2 - l1;
l0++;
}
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
while (i <= mid)
tmp[k++] = nums[i++];
while (j <= r)
tmp[k++] = nums[j++];
for (int i = l; i <= r; ++i)
nums[i] = tmp[i];
}
int countRangeSum(vector<int> &nums, int lower, int upper)
{
int n = nums.size();
this->lower = lower;
this->upper = upper;
vector<long long> sum(n + 1, 0);
for (int i = 0; i < n; ++i)
{
sum[i + 1] = sum[i] + nums[i];
}
n++;
tmp.resize(n);
merge_sort(sum, 0, n - 1);
return ans;
}
};
|