题目描述：
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
数据范围：
$1\le arr.len \le 3\times 10^4$
题解：
与 828. 统计子串中的唯一字符 | Luobuyu’s Blog 以及 2916. 子数组不同元素数目的平方和 II - 力扣（LeetCode） 类似。
有两种做法，一种是统计单个元素的贡献；另一种是使用 $dp$ ，考虑加入一个新元素之后，增加了哪些子数组，考虑增加的贡献。
计数原理：
首先需要确定每个元素作为最小值时，左侧和右侧的长度。
也就是需要统计出来每个元素左侧和右侧的比他小的元素的下标。统计比他小的，可以使用单调增栈。
假设 left[i],right[i] 表示 arr[i] 左侧和右侧比他小的元素的下标。初始化为 -1, n，方便统一处理。
需要特别注意相等元素，假设数组为 [1,2,2]。那么子数组为 [1],[1,2],[1,2,2] = 1*3, [2],[2,2] = 2*2,[2] = 2*1。
相等的最右侧需要找到严格小于他的，但是左侧只能找到小于等于他的。否则就是出现重复，比如 [2],[2,2]，[2(1), 2(2)],[2]。
最后的答案就是 (i - left[i]) * (right[i] - i) * arr[i]，次数乘以贡献。
dp
假设 $dp[i]$ 为所有以 $arr[i]$ 结尾的子数组的贡献之和。
对于 $dp[i]$ 来说，考虑从 $dp[i-1]$ 末尾加入 $arr[i]$ 之后是如何变化的。
加入 $arr[i]$ 之后，增加了所有以 $arr[i]$ 结尾的贡献，如果子数组中元素有比 $arr[i]$ 小的，那么贡献就是原来的，否则贡献就要算 $arr[i]$ 的。
因此需要找出来 $arr[i]$ 前一个比 $arr[i]$ 小的元素的下标 $p$ 。 $p$ 以及 $p$ 之前的为起点的子数组贡献都是原来的贡献，就是 $dp[p]$ 。 $p$ 之后为起点的子数组贡献都是 $arr[i]$ 的，即 $(i - p)\times arr[i]$ 。
代码：
两次单调栈版本
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int sumSubarrayMins(vector<int> &arr)
{
int top = -1;
int n = arr.size();
vector<int> st(n);
vector<int> right(n, n);
for (int i = 0; i < n; ++i)
{
while (top >= 0 && arr[st[top]] > arr[i])
{
right[st[top]] = i;
--top;
}
st[++top] = i;
}
vector<int> left(n, -1);
top = -1;
for (int i = n - 1; i >= 0; --i)
{
while (top >= 0 && arr[st[top]] >= arr[i])
{
left[st[top]] = i;
--top;
}
st[++top] = i;
}
long long ans = 0;
for (int i = 0; i < n; ++i)
{
ans = (ans + 1ll * (i - left[i]) * (right[i] - i) % mod * arr[i] % mod) % mod;
}
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int sumSubarrayMins(vector<int> &arr)
{
int top = -1;
int n = arr.size();
vector<int> st(n);
vector<int> right(n, n);
vector<int> left(n, -1);
for (int i = 0; i < n; ++i)
{
while (top >= 0 && arr[st[top]] > arr[i])
{
int pre = st[top];
right[st[top]] = i;
--top;
if (top >= 0)
left[pre] = st[top];
}
st[++top] = i;
}
int pre = st[top];
--top;
while (top >= 0)
{
left[pre] = st[top];
pre = st[top];
--top;
}
long long ans = 0;
for (int i = 0; i < n; ++i)
{
ans = (ans + (i - left[i]) * (right[i] - i) % mod * arr[i] % mod) % mod;
}
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int sumSubarrayMins(vector<int> &arr)
{
int n = arr.size();
vector<int> dp(n);
vector<int> st(n), left(n, -1);
int top = -1;
for (int i = n - 1; i >= 0; --i)
{
while (top >= 0 && arr[st[top]] >= arr[i])
{
left[st[top]] = i;
--top;
}
st[++top] = i;
}
long long ans = 0;
for (int i = 0; i < n; ++i)
{
int p = left[i];
if (p != -1)
dp[i] = (dp[p] + (i - p) * arr[i] % mod) % mod;
else
dp[i] = (i + 1) * arr[i] % mod;
ans = (ans + dp[i]) % mod;
}
return ans;
}
};
|