No Time to Paint (USACO Silver 2021 January)

首先考虑直接模拟：从左向右扫描，一个字母开始画了之后，如果后面只有比它大的字母，则这个字母可以继续画下去，这样显然更节省画的总次数。但如果后面出现比它小的字母（比如B后面出现了A），那B就不能继续画下去了，下次再碰到B，就需要重新画。所以我们可以简单地用一个数组来跟踪所有26个字母是否“活跃”，每次将当前字母后面的所有字母都reset为不活跃，就可以完成模拟了（下面程序中solve()就是模拟过程）。总复杂度 $\mathcal{O}(NQ)$ 。

因为 $N, Q \leq 10^5$ ，所以会有后面几个测试点不通过。

解决的办法也比较简单，就是预先计算所有前缀和后缀的结果，前缀从左向右算，后缀从右向左算（观察到两个方向计算结果是一样的），这样预计算把结果保存下来，就可以 $\mathcal{O}(1)$ 回答每次询问了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, q;
int a, b;
char s[100005];
int l2r[100005], r2l[100005];  // 从左到右，从右到左的预计算结果
bool on[26];                   // 跟踪所有26个字母是否“活跃”
 
void solve(int l, int r, int d, int *res) {
    int a = 0;
    memset(on, 0, sizeof(on));
    for (int i = l; ; i+=d) {
        int j = s[i]-'A';
        if (!on[j]) {
            on[j] = true;
            a++;
        }
        for (int k = j+1; k < 26; k++)   // reset j之后的所有字母
            on[k] = false;
        res[i] = a;
        if (i == r) break;
    }
}
 
int main() {
    scanf("%d %d", &n, &q);
    scanf("%s", s+1);
    solve(1, n, 1, l2r);
    solve(n, 1, -1, r2l);
 
    while (q--) {
        scanf("%d %d", &a, &b);
        int ans = 0;
        if (a > 1) ans += l2r[a-1];
        if (b < n) ans += r2l[b+1];
        printf("%d\n", ans);
    }
    return 0;
}