题解：UVA12572 RMQ Overkill

· · 题解

吐槽一下：题面复制不全，需要阅读 PDF 才能看懂题意。 ::::info[题意]{open} 给定一个由数字组成的字符串，询问其中每个子串中出现过的最小的一位数字和。 :::: 由于数据规模不能支持我们真的去查询每个子串（或者像原题所说的区间），我们需要一些更好的查询方式。

我们注意到一个区间的最小值取决于区间的最小值（废话），那么反过来看，是不是区间的最小值决定了区间的最小值（并非废话）？换句话说，考虑每个位置的值能够决定多少个区间的最小值，也就是对答案产生了多少贡献，就可以快速地统计最终答案了。

考虑一个问题：在一个区间中，有若干个点被打上了标记，那么至少包含有一个标记的点的区间有多少个？对于这个问题，为了不重复不遗漏地统计，我们考虑对每个标记点，钦定其为区间中最右边的标记点，假设这个区间为 [l,r] 且当前考虑的标记点下标为 i 并且下一个标记点下标为 j （如果没有下一个标记点，则认为 j 是正无穷）的话，合法的区间左端点在 [l,i] 之间，合法的区间端点在 [i,\min(j,r)] 之间。对于每个标记点，预处理出下一个标记点即可，预处理复杂度是 O(n) 的，可以看代码。

注意到数据范围，数字范围是 [0,9]，取值范围只有10，那么只用考虑 10 次不同标记就可以完成答案的计算了，复杂度 O(10n)=O(n)。从小到大考虑数字，并且让当前标记的数字分割区间（因为考虑更大的数字时，区间不能有比正在考虑的数字更小的数字），再进行下一个数字的考虑即可。我简单地模拟一下过程就好理解了。

::::info[模拟过程]

4
1231

我们先考虑完整区间以及数字 0，发现没有数字 0。

接下来考虑完整区间以及数字 1，发现第一位（下标个人习惯从 1 开始）是数字 1，下一个数字 1 在第四位，所以第一位的一贡献了 1\times3 个区间，答案加三。

接下来考虑第四位的数字 1，后面没有数字 1 了，贡献了 4\times1 个区间，答案加四。

接下来考虑区间 [2,3] 以及数字 2。为什么是这个小区间呢，因为接下来要标记的数字是 2，区间里就不能包含小于 2 的数字了，否则计算贡献时会多计算某些包含 1 的区间。详细过程略去，贡献 1\times2 个区间，答案加 1\times2\times2，最后乘上 2 是因为这些区间的最小值都是 2 了。

接下来考虑区间 [3,3] 以及数字 3，算得贡献为 1\times1，答案加 1\times1\times3。

我们得到最终答案为 14。 ::::

代码如下：

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
string s;
ll n,answer,a[10004],last[10],jump[10004];
void f(ll l,ll r,ll k)
{
    if(l>r||k>9)return;
    ll lastl=l;
    for(ll i=l;i<=r;i++)
    {
        if(a[i]==k)
        {
            answer+=k*(i-l+1)*(min(jump[i]-1,r)-i+1);
            answer%=MOD;
            f(lastl,i-1,k+1);//考虑更小的区间和更大的标记数字
            lastl=i+1;//考虑更大数字时要绕过当前位
        }
    }
    f(lastl,r,k+1);
}
int main()
{
    while(cin>>n)
    {
        answer=0;
        cin>>s;
        for(ll i=0;i<n;i++)a[i+1]=s[i]-'0';//string->integers
        memset(last,127,sizeof(last));
        for(ll i=n;i>=1;i--)//预处理下一次出现本数字的位置
        {
            jump[i]=last[a[i]];
            last[a[i]]=i;
        }
        f(1,n,0);
        cout<<answer<<'\n';
    }
}

最后斗胆评价一下题目难度，刚好是在我的舒适区内，能很快看出来但又要多想两下的程度，应该是普及+/提高左右？