题解

冷知识，这题和 KMP 算法有 $0$ 个关系。

注意到 M 只有一个，而一个 KMP 的子序列必须需要一个 M 前面的 K，M，M 之后的 P，所以我们不妨编个样例：

$\tt \color{black}KAPTAPPKKRMWYSWDPPHIGROSQIDONGP$

能够组成的 KMP 子序列有：

$\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGP$
$\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGP$
$\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}P$

$$$$

$\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGP$
$\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGP$
$\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}P$

$$$$

$\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGP$
$\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGP$
$\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}P$

可以发现总共子序列数量就是 M 之前的 K 的数量和 M 之后 P 的数量之积。

#include <iostream>
#include <cstdio>
#include <cstring> 
#define int long long
using namespace std;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	int idx = s.find('M');
	int ct1 = 0, ct2 = 0;
	for(int i = 0; i < idx; i++){
		if(s[i] == 'K') ct1++;
	}
	for(int i = idx + 1; i < s.size(); i++){
		if(s[i] == 'P') ct2++;
	}
	cout << ct1 * ct2;

	return 0;
}

时间复杂度 $O(|s|)$。

好了，你已经学会这一题了，现在来完成这一题吧：三元上升子序列_信奥算法普及+/提高-ACGO题库
hints：树状数组可以当做集合使用，可以以 $O(\log V)$ 的时间复杂度快速往集合内加入、删除一个不超过 $V$ 的元素，查询集合内小于等于某个元素的数量。