UVa 12572 RMQ Overkill

题目描述给定一个长度为NNN1≤N≤100001 \leq N \leq 100001≤N≤10000的非负整数序列每个元素的值小于101010。对于所有满足0≤i≤jN0 \leq i \leq j N0≤i≤jN的子区间(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总和11143313 1 1 1 4 3 3 1311143313。题目分析直接做法的复杂度最直接的想法是枚举所有子区间对每个子区间扫描求最小值。子区间的数量为N(N1)2\frac{N(N1)}{2}2N(N1)​当N10000N 10000N10000时子区间数量约为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×24 2 \times 2 42×24验证(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)时间内找到每个元素左右两侧第一个比它小或小等于的元素位置。算法步骤左侧扫描维护一个单调递增栈栈底到栈顶递增找左边第一个严格小于当前元素的位置右侧扫描维护一个单调递增栈找右边第一个小于等于当前元素的位置计算贡献对每个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)取模对109710^971097取模时间复杂度每个元素入栈出栈各一次O(N)O(N)O(N)总复杂度O(N)O(N)O(N)可以轻松应对N10000N10000N10000且120120120组数据完整代码// RMQ Overkill// UVa ID: 12572// Verdict: Accepted// Submission Date: 2026-05-21// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMOD1000000007;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;string s;while(cinns){// 将字符数组转换为整数数组vectorinta(n);for(inti0;in;i)a[i]s[i]-0;vectorintleft(n),right(n);stackintst;// 第一步找左边第一个严格小于 a[i] 的位置for(inti0;in;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(intin-1;i0;--i){while(!st.empty()a[st.top()]a[i])st.pop();right[i]st.empty()?n:st.top();st.push(i);}// 第三步累加每个元素作为最小值的贡献longlongans0;for(inti0;in;i){longlongcnt(longlong)(i-left[i])*(right[i]-i);ans(ansa[i]*cnt)%MOD;}coutans\n;}return0;}总结方法时间复杂度空间复杂度是否可行暴力枚举O(N3)O(N^3)O(N3)O(1)O(1)O(1)❌ 超时预处理区间最小值O(N2)O(N^2)O(N2)O(N2)O(N^2)O(N2)❌ 内存超限单调栈贡献计数O(N)O(N)O(N)O(N)O(N)O(N)✅ 完美通过本题的核心技巧是“贡献计数”与“单调栈”的结合。通过将问题从“枚举所有区间”转化为“统计每个元素作为最小值的次数”再利用单调栈快速找到左右边界成功将复杂度降至线性。这种思维方式在区间最值相关问题中非常常见例如“直方图最大矩形”、“所有子数组最小值之和”等经典题目都使用了类似的思想。