UVa 12572 RMQ Overkill

题目描述

给定一个长度为NNN（1≤N≤100001 \leq N \leq 100001≤N≤10000）的非负整数序列，每个元素的值小于101010。对于所有满足0≤i≤j<N0 \leq i \leq j < N0≤i≤j<N的子区间(i,j)(i, j)(i,j)，求出该区间的最小值，然后将所有这些最小值求和，最后对100000000710000000071000000007取模输出。

输入包含多组测试用例（不超过120120120组），每组用例第一行是NNN，第二行是一个长度为NNN的数字字符串。

样例分析

样例输入

3 143 3 413 3 121

样例输出

13 11 7

以第一个样例143为例：

• 子区间(0,0)(0,0)(0,0)最小值111
• 子区间(0,1)(0,1)(0,1)最小值111
• 子区间(0,2)(0,2)(0,2)最小值111
• 子区间(1,1)(1,1)(1,1)最小值444
• 子区间(1,2)(1,2)(1,2)最小值333
• 子区间(2,2)(2,2)(2,2)最小值333

总和=1+1+1+4+3+3=13= 1 + 1 + 1 + 4 + 3 + 3 = 13=1+1+1+4+3+3=13。

题目分析

直接做法的复杂度

最直接的想法是枚举所有子区间，对每个子区间扫描求最小值。子区间的数量为：

N(N+1)2\frac{N(N+1)}{2}2N(N+1)​

当N=10000N = 10000N=10000时，子区间数量约为5×1075 \times 10^75×107，对每个区间求最小值又会增加O(N)O(N)O(N)的时间，显然会超时。

核心思路：贡献计数法

我们不能枚举区间，而应该换个角度：枚举每个元素，计算它作为最小值出现在多少个区间中。

对于位置iii上的元素a[i]a[i]a[i]，如果我们可以知道：

• 向左最多能延伸到多远，使得a[i]a[i]a[i]仍然是该区间的最小值
• 向右最多能延伸到多远，使得a[i]a[i]a[i]仍然是该区间的最小值

那么包含iii且以a[i]a[i]a[i]为最小值的子区间数量 = (左侧可延伸长度) × (右侧可延伸长度)。

边界处理技巧（去重）

当数组中有相同元素时，需要小心处理，避免同一个区间的最小值被重复计算。

常用策略：

• 向左找第一个严格小于a[i]a[i]a[i]的元素（遇到相等的就停下）
• 向右找第一个小于等于a[i]a[i]a[i]的元素（遇到相等的继续）

这样每个子区间的最小值只会被最左边那个最小值元素统计到，保证不重不漏。

图解说明

假设数组为[2, 5, 3, 3, 1]，考虑中间的333（下标222）：

下标:01234值:25331

• 向左找第一个严格小于333的元素：下标000的222，所以左边界是000（实际左侧延伸从111开始）
• 向右找第一个小于等于333的元素：下标444的111，所以右边界是444（实际右侧延伸到333）

那么包含下标222且以333为最小值的区间：

• 左端点可选：1,21, 21,2（共222种）
• 右端点可选：2,32, 32,3（共222种）
• 总区间数=2×2=4= 2 \times 2 = 4=2×2=4

验证：(1,2)(1,2)(1,2)、(1,3)(1,3)(1,3)、(2,2)(2,2)(2,2)、(2,3)(2,3)(2,3)最小值都是333。

高效算法：单调栈

单调栈可以在O(N)O(N)O(N)时间内找到每个元素左右两侧第一个比它小（或小等于）的元素位置。

算法步骤

1. 左侧扫描：维护一个单调递增栈（栈底到栈顶递增），找左边第一个严格小于当前元素的位置
2. 右侧扫描：维护一个单调递增栈，找右边第一个小于等于当前元素的位置
3. 计算贡献：对每个iii，累加a[i]×(i−left[i])×(right[i]−i)a[i] \times (i - left[i]) \times (right[i] - i)a[i]×(i−left[i])×(right[i]−i)
4. 取模：对109+710^9+7109+7取模

时间复杂度

• 每个元素入栈出栈各一次，O(N)O(N)O(N)
• 总复杂度O(N)O(N)O(N)，可以轻松应对N=10000N=10000N=10000且120120120组数据

完整代码

// RMQ Overkill// UVa ID: 12572// Verdict: Accepted// Submission Date: 2026-05-21// UVa Run Time: 0.010s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMOD=1000000007;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;string s;while(cin>>n>>s){// 将字符数组转换为整数数组vector<int>a(n);for(inti=0;i<n;++i)a[i]=s[i]-'0';vector<int>left(n),right(n);stack<int>st;// 第一步：找左边第一个严格小于 a[i] 的位置for(inti=0;i<n;++i){while(!st.empty()&&a[st.top()]>=a[i])st.pop();left[i]=st.empty()?-1:st.top();st.push(i);}// 清空栈，准备右侧扫描while(!st.empty())st.pop();// 第二步：找右边第一个小于等于 a[i] 的位置for(inti=n-1;i>=0;--i){while(!st.empty()&&a[st.top()]>a[i])st.pop();right[i]=st.empty()?n:st.top();st.push(i);}// 第三步：累加每个元素作为最小值的贡献longlongans=0;for(inti=0;i<n;++i){longlongcnt=(longlong)(i-left[i])*(right[i]-i);ans=(ans+a[i]*cnt)%MOD;}cout<<ans<<'\n';}return0;}

总结

本题的核心技巧是“贡献计数”与“单调栈”的结合。通过将问题从“枚举所有区间”转化为“统计每个元素作为最小值的次数”，再利用单调栈快速找到左右边界，成功将复杂度降至线性。

这种思维方式在区间最值相关问题中非常常见，例如“直方图最大矩形”、“所有子数组最小值之和”等经典题目都使用了类似的思想。