把 C[i][j] 恒等变形为 (A[i]+i)(B[j]+j),行列最大值即可分离,再用单调栈统计每个元素被各长度窗口计入的次数、差分还原全部 F[k]。
OJ: roj
题目 ID: 1749
难度:提高+/省选-
标签:单调栈数学计数python
创建: 2026-10-07 21:10
更新: 2026-10-07 21:10
形式化题目
给定长度
一个矩阵的价值定义为其中最大元素的值。对每个
中所有 连续子矩阵(行窗 、列窗 )的价值之和。
求
正解
思路
第一步:把矩阵"拆开"。 题面给的
令
第二步:行列分离。 题目保证
两个因子都取最大时乘积才最大,行与列的选择互不干扰。于是
问题化归为一个经典子问题:给定数组,对每个
第三步:
为了不重不漏,规定每个区间由它最靠右的那个最大值代表。用单调栈求出
: 左侧最近的满足 的位置(严格大于,不存在则为 ); : 右侧最近的满足 的位置(大于等于,不存在则为 )。
这两侧口径一严一松,正好保证"每个区间恰有一个最右最大值"。记
也就是
要求
第四步:把
对固定的
slope[k]:的系数之和; const[k]:常数项之和。
于是最终 slope 区间加 const 区间加 slope 区间加 const 区间加
注意全程可以在模
下面用样例展示前两步的分离:
flowchart LR
A["A = 4 1 9"] --> X["X = A_i + i<br/>= 5 3 12"]
B["B = 3 4 1"] --> Y["Y = B_j + j<br/>= 4 6 4"]
X --> SX["S_X = 20, 17, 12"]
Y --> SY["S_Y = 14, 12, 6"]
SX --> F["F = 20*14, 17*12, 12*6<br/>= 280, 204, 72"]
SY --> F
以样例的
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:05
# update_at: 2026-10-07 21:05
import sys
MOD = 10 ** 9 + 7 # 题目要求的取模数
def add_range(d: list[int], l: int, r: int, v: int) -> None:
"""在差分数组 d 的闭区间 [l, r] 上整体加 v;l > r 时是空区间,直接跳过。"""
if l > r or v == 0:
return
d[l] = (d[l] + v) % MOD
d[r + 1] = (d[r + 1] - v) % MOD
def window_max_sum(arr: list[int]) -> list[int]:
"""回答:arr 的所有长度 k 子区间的最大值之和是多少(k = 1..n,对 MOD 取模)。
每个区间只由它「最右边的那个最大值」代表。下标 i 是区间 [s, e] 的最右最大值,
当且仅当 L[i] < s <= i <= e < R[i],其中 L 是左侧最近的严格更大位置、
R 是右侧最近的大于等于位置。于是 arr[i] 被长度 k 的区间计入
cnt(k) = min(k, a, b, a+b-k),a = i - L[i],b = R[i] - i,
它关于 k 分三段线性,用两个差分数组一次求出全部 k 的答案。
"""
n = len(arr) - 1
lef = [0] * (n + 1)
rig = [n + 1] * (n + 2)
stk: list[int] = [] # 单调递减栈,存下标
for i in range(1, n + 1):
while stk and arr[stk[-1]] <= arr[i]:
stk.pop()
lef[i] = stk[-1] if stk else 0
stk.append(i)
stk.clear()
for i in range(n, 0, -1):
while stk and arr[stk[-1]] < arr[i]:
stk.pop()
rig[i] = stk[-1] if stk else n + 1
stk.append(i)
slope = [0] * (n + 3) # 差分:k 的系数
const = [0] * (n + 3) # 差分:常数项
for i in range(1, n + 1):
v = arr[i] % MOD
a, b = i - lef[i], rig[i] - i
small, big = min(a, b), max(a, b)
last = a + b - 1 # cnt(k) > 0 的最大 k
add_range(slope, 1, small, v) # cnt = k
add_range(const, small + 1, big, v * small % MOD) # cnt = small
add_range(const, big + 1, last, v * (a + b) % MOD) # cnt = a+b-k
add_range(slope, big + 1, last, (-v) % MOD)
out = [0] * (n + 1)
s1 = s2 = 0 # 斜率前缀、常数前缀
for k in range(1, n + 1):
s1 = (s1 + slope[k]) % MOD
s2 = (s2 + const[k]) % MOD
out[k] = (s1 * k + s2) % MOD
return out
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
a = [next(data) for _ in range(n)]
b = [next(data) for _ in range(n)]
# C[i][j] = (A[i] + i) * (B[j] + j),两因子恒正,故行列最大值可分开算
x = [0] + [v + i for i, v in enumerate(a, 1)]
y = [0] + [v + i for i, v in enumerate(b, 1)]
sx = window_max_sum(x)
sy = window_max_sum(y)
ans = [sx[k] * sy[k] % MOD for k in range(1, n + 1)]
print(" ".join(map(str, ans)))
if __name__ == "__main__":
solve()C++ 版:
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 21:05
* update_at: 2026-10-07 21:05
*
* 一本通 1749《矩阵求和》
*
* 关键恒等变换:C[i][j] = A[i]*B[j] + i*B[j] + A[i]*j + i*j = (A[i]+i)*(B[j]+j)。
* 令 X[i] = A[i]+i, Y[j] = B[j]+j,由于 0 <= A,B 且下标从 1 起,X、Y 恒正,
* 于是 k*k 子矩阵的最大值 = 行窗 X 最大值 * 列窗 Y 最大值,行列互不影响:
* F[k] = (所有长度 k 的 X 窗最大值之和) * (所有长度 k 的 Y 窗最大值之和)。
* 剩下的子问题「所有长度 k 子区间最大值之和」用单调栈统计每个元素作为
* 最右最大值时的贡献区间数,贡献数关于 k 分段线性,用两个差分数组一次求出全部 k。
* 时间 O(n),空间 O(n)。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
const int MAXN = 100005;
ll a[MAXN], b[MAXN];
ll x[MAXN], y[MAXN]; // x[i] = a[i] + i, y[i] = b[i] + i
int lef[MAXN], rig[MAXN]; // 左侧最近的严格更大位置、右侧最近的大于等于位置
int stk[MAXN]; // 单调栈,存下标
ll slope[MAXN]; // 差分数组:k 的系数
ll constant[MAXN]; // 差分数组:常数项
ll sx[MAXN], sy[MAXN]; // 两个数组的「长度 k 窗最大值之和」
// 对差分数组 d 在区间 [l, r] 上加 v(v 已对 MOD 取模)
void add_range(ll d[], int l, int r, ll v) {
if (l > r || v == 0) return;
d[l] = (d[l] + v) % MOD;
d[r + 1] = (d[r + 1] - v + MOD) % MOD;
}
// 求 arr 所有长度 k 子区间最大值之和,k = 1..n,结果对 MOD 取模写入 out[1..n]
void window_max_sum(ll arr[], int n, ll out[]) {
// 左侧最近的严格大于 arr[i] 的位置(无则 0)
int top = 0;
for (int i = 1; i <= n; i++) {
while (top > 0 && arr[stk[top]] <= arr[i]) top--;
lef[i] = (top > 0) ? stk[top] : 0;
stk[++top] = i;
}
// 右侧最近的大于等于 arr[i] 的位置(无则 n+1)
top = 0;
for (int i = n; i >= 1; i--) {
while (top > 0 && arr[stk[top]] < arr[i]) top--;
rig[i] = (top > 0) ? stk[top] : n + 1;
stk[++top] = i;
}
for (int i = 0; i <= n + 1; i++) {
slope[i] = 0;
constant[i] = 0;
}
// 记 a = i - lef[i],b = rig[i] - i。arr[i] 恰是区间 [s,e] 的最右最大值
// 当且仅当 lef[i] < s <= i <= e < rig[i],故它被长度 k 的区间计入的次数
// cnt(k) = min(k, a, b, a+b-k) (1 <= k <= a+b-1)
// 该函数关于 k 分三段线性:k 段、常数 m 段、a+b-k 段。
for (int i = 1; i <= n; i++) {
ll v = arr[i] % MOD;
int a = i - lef[i];
int b = rig[i] - i;
int m = min(a, b);
int big = max(a, b);
int last = a + b - 1; // cnt(k) > 0 的最大 k
add_range(slope, 1, m, v); // cnt = k
add_range(constant, m + 1, big, v * m % MOD); // cnt = m
add_range(constant, big + 1, last, v * ((a + b) % MOD) % MOD); // cnt = a+b-k
add_range(slope, big + 1, last, (MOD - v) % MOD);
}
// 前缀和还原出 f(k) = (斜率前缀) * k + (常数前缀)
ll s1 = 0, s2 = 0;
for (int k = 1; k <= n; k++) {
s1 = (s1 + slope[k]) % MOD;
s2 = (s2 + constant[k]) % MOD;
out[k] = (s1 * (k % MOD) + s2) % MOD;
}
}
int main() {
int n;
if (scanf("%d", &n) != 1) return 0;
for (int i = 1; i <= n; i++) {
if (scanf("%lld", &a[i]) != 1) return 0;
x[i] = a[i] + i;
}
for (int i = 1; i <= n; i++) {
if (scanf("%lld", &b[i]) != 1) return 0;
y[i] = b[i] + i;
}
window_max_sum(x, n, sx);
window_max_sum(y, n, sy);
for (int k = 1; k <= n; k++) {
ll ans = sx[k] * sy[k] % MOD;
if (k < n) printf("%lld ", ans);
else printf("%lld\n", ans);
}
return 0;
}复杂度
- 时间:每个数组一次单调栈
+ 每个位置 次差分区间加 + 一次前缀和,两个数组共 。 - 空间:
、栈、两个差分数组与原数组均为 。
正确性要点与边界
- 正数前提不能省。 若允许
为负, 可能非正,"乘积取最大 = 两因子分别取最大"就不成立。本题 且 ,故 ,这一步是合法的。 - 去重口径一严一松。
用"严格大于"、 用"大于等于",否则大量并列值(例如 时 严格递增,或 时 全相等)会被重复计数或漏计。两处口径写反不会影响题目样例(样例的 无并列),但会在有并列值的数据上算错——实测把两处口径互换后,测试点 3、7、8、10 的答案立即改变,其中点 10( 全相等)是最极端的一例。 - 差分数组要开到
。 区间右端点可达 ,在 d[r+1]处会越界写入,数组必须留出余量;同时add_range需处理的空区间。 - 取模位置。 差分区间加时
要先对 取模,减法写成加 再取模; const上的量中 可到 , 可到 ,乘积约 ,C++ 需用 long long(Python 无此问题)。 - 输出格式。 一行
个整数,用空格分隔、行尾换行,注意不要在行末多输出空格(多数判题器容忍,但严格比较的判题器会判错)。
总结
- 先化简再优化。 四项展开式其实是
,识别出"外积矩阵"后, 个元素的最大值问题就塌缩成两个一维问题,这是本题最关键的一步,也是唯一需要"看出"的地方。 - 正数乘积可分离极值。
只在两个因子恒正时成立;题面刻意给出 正是为了让这一步合法,反过来看也是题面在暗示解法。 - 从"枚举区间"转向"枚举元素"。 对每个
扫一遍是 ,改让每个元素统计自己被多少个窗口计入,就把 个元素的贡献分别变成 次区间加,这是"所有子区间极值之和"这类题的通用套路。 - 单调栈的口径决定计数是否唯一。
严格大于、 大于等于,才能让每个区间恰有一个"最右最大值"来代表;并列值越多,这个细节越致命。 - 分段线性函数用差分数组承载。 贡献函数
是"上凸的折线",两段斜率变化 + 一段常数,用 slope/const两个差分数组即可一次求出全部,不需要任何数据结构。
关于本题数据的说明:仓库素材源中带有测试数据生成脚本(
data.py,依赖cyaron),说明data/下 10 个测试点是由标程自造的,并非官方原始数据;题面也属于网络重建版本。因此上述「分层设计」描述的是本仓库数据的构造意图,出题意图与官方原题可能存在偏差,题解结论以题面公式与数据范围为准(已用main.cpp/main.py与全部 10 个测试点逐点比对一致)。