题目描述

思路

我们可以把这道题的输入数据想象成一个一座山，有很多个山峰和山谷。

我们从左往右计算，如果正在上山，那么答案增加一。下山的时候，如果这个点在上山的时候已经出现过了，就不统计，只是消除比这个点高的点的记录（因外后面如果出现比这个点高的点，那么也不是这座山峰了），否则统计。

我们发现这个其实可以做成前缀和，如果想获得从第一个到第 $i$ 个点的答案就按前缀和去计算。

回到题目，我们发现一整座山有可能被空白的分隔成两座了，对于左边的的那座山，可以直接计算。但是对于右边的山，我们无法确定这个山有哪些点被统计过，所以这道题我们之前统计的数组没法按前缀和去计算任意区间答案，所以我们采取从后往前的前缀和来处理。

以后遇到前缀和无法计算任意区间的答案，但是可以计算从 $1$ 开始的，而且题目只需要求从第一个开始的或者从最后一个结束的，或者题目可以变幻成这样的形式的，我们都可以用两个前缀和来做。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
/*
*/
int a[1000005];
int b[1000005], p1[1000005], p2[1000005], vis[1000005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    string s; cin >> s;
    for (int i = 1; i <= n; i ++) a[i] = s[i - 1] - 'A' + 1;
    for (int i = 1; i <= n; i ++) {
        if (a[i - 1] < a[i] || i == 1) p1[i] = 1, vis[a[i]] = 1;
        else if (a[i - 1] > a[i]) {
            p1[i] = (vis[a[i]] ? 0 : 1);
            vis[a[i]] = 1;
            for (int j = a[i] + 1; j <= 27; j ++) {
                vis[j] = 0;
            }
        }
    }
    memset(vis, 0, sizeof(vis));
    for (int i = n; i >= 1; i --) {
        if (a[i + 1] < a[i] || i == n) p2[i] = 1, vis[a[i]] = 1;
        else if (a[i + 1] > a[i]) {
            p2[i] = (vis[a[i]] ? 0 : 1);
            vis[a[i]] = 1;
            for (int j = a[i] + 1; j <= 27; j ++) {
                vis[j] = 0;
            }
        }
    }
    for (int i = n; i >= 1; i --) p2[i] += p2[i + 1];
    for (int i = 1; i <= n; i ++) p1[i] += p1[i - 1];
    for (int i = 1; i <= q; i ++) {
        int x, y; cin >> x >> y;
        int ans = 0;
        if (x != 1) ans += p1[x - 1];
        if (y != n) ans += p2[y + 1];
//      if (x == 1) ans --;
//      if (y == n) ans --;
        cout << ans << "\n";
    } 
    return 0;
}