题目描述
思路
我们可以把这道题的输入数据想象成一个一座山,有很多个山峰和山谷。
我们从左往右计算,如果正在上山,那么答案增加一。下山的时候,如果这个点在上山的时候已经出现过了,就不统计,只是消除比这个点高的点的记录(因外后面如果出现比这个点高的点,那么也不是这座山峰了),否则统计。
我们发现这个其实可以做成前缀和,如果想获得从第一个到第 $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;
}