固定右端点，用两个单调栈找出极值变化点并按窗口长度差分入账，O(n×值域) 求出全部 n 个窗口值
OJ: roj
题目 ID: 10003
难度:普及+/提高-
标签:单调栈差分python
创建: 2026-10-02 17:20
更新: 2026-10-07 12:15
形式化题目
给定长度为
并按
样例 55 35 23 15 5。
正解
思路
朴素做法撑不住。 最直接的写法是枚举每个子数组、各自求
换一个枚举顺序。 固定右端点
top <= x，相等值只留更靠右那个，而相等不会改变
数据范围
段按长度差分入账。 一段左端点区间 d[lo] += prod、d[hi+1] -= prod，每段 d[1..n] 做一次前缀和，得到 d[i-left+1] += prod、d[i-nxt+1] -= prod；最后剩下的左端点区间是 d[i+2]，差分数组开到 n+3 才够。
下面用样例
| 右端点 |
左端点 |
窗口长度 |
计入 | |||
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | |
| 2 | 2 | 1 | 5 | 5 | 25 | |
| 2 | 1 | 2 | 5 | 1 | 5 | |
| 3 | 3 | 1 | 2 | 2 | 4 | |
| 3 | 2 | 2 | 5 | 2 | 10 | |
| 3 | 1 | 3 | 5 | 1 | 5 | |
| 4 | 4 | 1 | 4 | 4 | 16 | |
| 4 | 3 | 2 | 4 | 2 | 8 | |
| 4 | 2 | 3 | 5 | 2 | 10 | |
| 4 | 1 | 4 | 5 | 1 | 5 | |
| 5 | 5 | 1 | 3 | 3 | 9 | |
| 5 | 4 | 2 | 4 | 3 | 12 | |
| 5 | 3 | 3 | 4 | 2 | 8 | |
| 5 | 2 | 4 | 5 | 2 | 10 | |
| 5 | 1 | 5 | 5 | 1 | 5 |
按列求和正好是 55 35 23 15 5。注意
同一下标同时刷新最大值和最小值
当某个 d[lo] += prod 与 d[hi+1] -= prod 落在同一格），自动抵消，随后两处极值都已更新。所以代码不需要对这种情况写特判，但必须保留这次「空入账」，否则会重复计一段。
一般情况下一段会覆盖多个长度。例如数组
| 段（左端点） | 窗口长度区间 |
乘积 | 差分操作 | ||
|---|---|---|---|---|---|
| 2 | 2 | 4 | d[1] += 4、d[2] -= 4 |
||
| 3 | 2 | 6 | d[2] += 6、d[4] -= 6 |
||
| 3 | 1 | 3 | d[4] += 3、d[5] -= 3 |
第二段说明了差分的价值：窗口
代码
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-02 17:25
# update_at: 2026-10-02 17:25
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
values = [next(data) for _ in range(n)]
# 按"窗口长度"下标做差分：d 是差分数组，前缀和后 d[L] 即第 L 窗口值。
# a_i <= 100，答案上界 1e5 * 100^2 = 1e9，直接输出，无需取模。
d = [0] * (n + 3)
# 两个单调栈存 (值, 下标)，栈内下标从栈顶往栈底递减：
# max 栈的值严格递减、min 栈的值严格递增，元素即"左端点左移时极值发生变化的位置"。
max_stack: list[tuple[int, int]] = []
min_stack: list[tuple[int, int]] = []
for i, x in enumerate(values):
while max_stack and max_stack[-1][0] <= x:
max_stack.pop()
while min_stack and min_stack[-1][0] >= x:
min_stack.pop()
max_stack.append((x, i))
min_stack.append((x, i))
cur_max = cur_min = x # 只含 a[i] 这一个左端点时的极值
left = i # 当前已登记的最左左端点
p_max = len(max_stack) - 2 # 指针停在栈顶的下一层：下一个极值变化点
p_min = len(min_stack) - 2
# 左端点从 i 往 0 走，逐个吞并两栈的变化点：
# 每一步 (cur_max, cur_min) 在左端点 (nxt, left] 上不变，把这段按长度差分入账。
while p_max >= 0 or p_min >= 0:
# 两栈都还有变化点时，先走下标更大的那个：更靠近 i 的变化先发生；
# 同一下标同时是 max/min 变化点时会退化出一段空区间，加减抵消，不影响答案。
take_max = p_max >= 0 and (p_min < 0 or max_stack[p_max][1] >= min_stack[p_min][1])
if take_max:
value, nxt = max_stack[p_max]
p_max -= 1
else:
value, nxt = min_stack[p_min]
p_min -= 1
prod = cur_max * cur_min
d[i - left + 1] += prod # 左端点 left 对应的窗口长度 = i-left+1
d[i - nxt + 1] -= prod # 左端点越过 nxt 后这对极值失效
left = nxt
if take_max:
cur_max = value
else:
cur_min = value
# 剩下左端点 [0, left] 全部落在同一对极值上，长度区间到 i+1 为止。
prod = cur_max * cur_min
d[i - left + 1] += prod
d[i + 2] -= prod
out: list[str] = []
total = 0
for length in range(1, n + 1):
total += d[length]
out.append(str(total))
sys.stdout.write(' '.join(out))
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-04 21:50
* update_at: 2026-10-04 21:50
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
typedef long long ll;
ll n;
int a[MAXN]; // 输入数组，a_i <= 100，用 int 控制内存
ll diff[MAXN + 3]; // diff 按窗口长度做差分，前缀和后 diff[L] 就是第 L 窗口值
// 单调栈元素：value 是极值，index 是它出现的下标。
struct StackNode {
ll value;
ll index;
};
StackNode max_stack[MAXN]; // 从右往左看的 max 记录值，值严格递减
StackNode min_stack[MAXN]; // 从右往左看的 min 记录值，值严格递增
void read_input() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> a[i];
}
}
// 固定右端点 i，让左端点从 i 往 1 左移，两栈按下标从大到小归并出极值不变的段，
// 每段对应一段连续的窗口长度，用差分 O(1) 入账。
void solve() {
ll max_top = 0; // max_stack 中元素个数，栈顶下标是 max_top
ll min_top = 0;
for (ll i = 1; i <= n; i++) {
ll x = a[i];
while (max_top > 0 && max_stack[max_top].value <= x) {
max_top--;
}
while (min_top > 0 && min_stack[min_top].value >= x) {
min_top--;
}
max_top++;
max_stack[max_top].value = x;
max_stack[max_top].index = i;
min_top++;
min_stack[min_top].value = x;
min_stack[min_top].index = i;
ll cur_max = x; // 只含左端点 i 时的极值
ll cur_min = x;
ll left = i; // 当前已入账的最左左端点
ll p_max = max_top - 1; // 栈顶的下一层即下一个极值变化点
ll p_min = min_top - 1;
while (p_max >= 1 || p_min >= 1) {
// 两栈都有变化点时先走下标更大的那个，因为更靠近 i 的变化先发生。
// 同一下标同时是 max/min 变化点时会退化成空区间，加减抵消，无需特判。
bool take_max = (p_max >= 1) && (p_min < 1 || max_stack[p_max].index >= min_stack[p_min].index);
ll value;
ll nxt;
if (take_max) {
value = max_stack[p_max].value;
nxt = max_stack[p_max].index;
p_max--;
} else {
value = min_stack[p_min].value;
nxt = min_stack[p_min].index;
p_min--;
}
ll prod = cur_max * cur_min;
diff[i - left + 1] += prod; // 左端点 left 对应窗口长度 i-left+1
diff[i - nxt + 1] -= prod; // 左端点越过 nxt 后这对极值失效
left = nxt;
if (take_max) {
cur_max = value;
} else {
cur_min = value;
}
}
// 剩下的左端点 [1, left] 极值都不再变化，长度上界是 i。
ll prod = cur_max * cur_min;
diff[i - left + 1] += prod;
diff[i + 1] -= prod;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
ll total = 0;
for (ll length = 1; length <= n; length++) {
total += diff[length];
if (length > 1) {
cout << ' ';
}
cout << total;
}
cout << '\n';
return 0;
}复杂度
- 时间：建栈每个元素进栈、弹栈各至多一次，
；每个右端点的走段数 ，合计 ，其中 ，即约 量级。真实数据栈更短（实测最大组 用时 0.13s）。 - 空间：差分数组
、输入输出 ，两个单调栈各至多 100 个元素，峰值约 32MB，低于 128MB 限制。 - 答案上界
，题面未要求取模，直接输出。
总结
- 朴素做法逐窗口求
是 起步，超时的根因是窗口总数为 。 - 换成「固定右端点、左端点左移」后，极值只在单调栈记录的变化点处改变，按变化点归并即可成段处理。
让两个栈（即每右端点的段数）至多各 100，整体 ，这是本题数据范围的隐藏用法。 - 每段对应连续的窗口长度，用差分数组
入账，末尾一次前缀和还原全部 个答案；同下标双变化靠空区间自然抵消，无需特判。